Link 总分：195/400 排名：7/20+
T1
分数：100
知识点：数学
思路：枚举每个点，连边，判断是否和 x 轴 y 轴平行，如平行就计算面积和答案比较。
Code
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const int maxn = 1e5+5;int n;
double ans = 0.0;
double x[105], y[105];
bool xie(double x1,double y1,double x2,double y2)
{return !((x1 == x2) || (y1 == y2));
}
double S(double bx,double by,double x1,double y1,double x2,double y2)
{return abs(x1-bx+y1-by)*abs(x2-bx+y2-by)/2;
}int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>x[i]>>y[i];for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){for(int k=j+1;k<=n;k++){// 如果边是斜着的, 肯定不会平行double x1 = x[i], y1 = y[i]; double x2 = x[j], y2 = y[j]; double x3 = x[k], y3 = y[k]; if(xie(x1,y1,x2,y2)+xie(x1,y1,x3,y3)+xie(x2,y2,x3,y3) != 1) continue;double t;if(xie(x1,y1,x2,y2)+xie(x1,y1,x3,y3) == 0) t = S(x1,y1,x2,y2,x3,y3);else if(xie(x1,y1,x2,y2)+xie(x2,y2,x3,y3) == 0) t = S(x2,y2,x1,y1,x3,y3);else t = S(x3,y3,x1,y1,x2,y2);
// cout<<"("<T2
分数：0
知识点：模拟
思路：按中心对称分成四格一组，每组独立。设组内有 k 个 #，代价为 min(k,4-k)。初始累加左上象限所有组；每次更新只影响所在组，增量更新答案即可。复杂度 O(N²+U)。
为什么没想到正解思路：没有发现每次操作只影响四格
Code
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const int maxn = 2000+5;int n,q,cnt = 0;
vector > f,res;int calc(int x,int y)
{int res = 0;if(!f[x][y]) res++;if(!f[n-x+1][y]) res++;if(!f[x][n-y+1]) res++;if(!f[n-x+1][n-y+1]) res++;return min(res,4-res);
}int ft()
{int ans = 0;for(int i=1;i<=n/2;i++){for(int j=1;j<=n/2;j++){ans += calc(i,j);}}return ans;
}int query(int x,int y)
{int t = calc(x,y);f[x][y] = !f[x][y];int res = calc(x,y);return res-t;
}int main()
{cin>>n>>q;f.assign(n+1, vector(n+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){char c;cin>>c;if(c == '#') f[i][j] = 1;else f[i][j] = 0; }}int ans = ft();cout<>x>>y;ans += query(x,y);cout<T3
分数：79
知识点：DFS
思路：把 n 不断除以斐波那契数，同时用 mx 限制因子单调不减，避免同一组合被重复枚举。
为什么没想到正解思路：没有剪去因子重复排列，导致复杂度过高
Code
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const int maxn = 1e5+5;int t,m;
ll n,cnt;
vector f;void init()
{// 因为 1 不行, 所以从 2, 3 开始 f.push_back(2);f.push_back(3);int n = 2;while(f.back() > 0 && f.back() <= 1e18){ll now = f[n-1]+f[n-2];f.push_back(now);n++;}
}void dfs(ll res, ll mx)
{if(res == 1) {cnt++;return;}for(ll m : f){if(mx > m) continue;if(m > res) return;if(res%m == 0) dfs(res/m, m);}
}int main()
{init();cin>>t;while(t--){cin>>n;cnt = 0; dfs(n,0);cout<T4
分数：16
知识点：最短路，二分
思路：新边 (u,v) 后最短路只可能是 min(原最短路, ds[u]+L+dt[v], ds[v]+L+dt[u])。先跑 S、T 两遍 Dijkstra，再对每个 u 二分统计满足 ds[u]+dt[v]+L≤K的 v 数量。特判原最短路已 ≤K 则全选。
为什么没想到正解思路：没有想到加入新边后最短路必定经过这条边
Code
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;int n,m,s,t;
ll l,k,ans;
ll dis[maxn], ds[maxn], dt[maxn];
vector g[maxn];
bool vis[maxn];void Dij(int s)
{memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s] = 0;priority_queue q;q.push({0,s});while(!q.empty()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = 1;for(int i=0;i>n>>m>>s>>t>>l>>k;for(int i=1;i<=m;i++){int u,v;ll w;cin>>u>>v>>w;g[u].push_back({w,v});g[v].push_back({w,u});}Dij(s);for(int i=1;i<=n;i++) ds[i] = dis[i];Dij(t);for(int i=1;i<=n;i++) dt[i] = dis[i];sort(dt+1,dt+1+n);if(ds[t] <= k){cout<<1ll*n*(n-1)/2;return 0;}// D(s,u) + l + D(v,t) < D(s,t)// D(t,v) < D(s,t) - l - D(s,u)for(int u=1;u<=n;u++) ans += (upper_bound(dt+1,dt+1+n,k-l-ds[u]) - dt - 1);cout<