test30
前两题都 0pts，nbm（？
2-A 飞船制造 (spaceship.cpp)
怎么有傻子没开 c++11 写了 rank 然后 re 惹 /fad
考虑依次枚举 \(s=i+j+k\)，计算出 \(s\) 一定的方案数就能确定唯一的 \(s\)，方案数计算好像只能考虑背包。然后依次枚举 \(i\)，计算出 \(s,i\) 一定时 \((j,k)\) 的方案数就能确定唯一的 \(i\)，方案数可以考虑 \(j\) 的上下界。然后依次枚举 \(j\)，不断增加排名直到符合题目要求即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=3000005;int n, rk, f[3][N];signed main() {
// freopen("1.txt","r",stdin);freopen("spaceship.in","r",stdin);freopen("spaceship.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> rk;up(i,1,3*n) f[0][i]=f[0][i-1]+(i<=n);up(i,1,3*n) f[1][i]=f[0][i-1]-(i-n-1>=0?f[0][i-n-1]:0);up(i,1,3*n) f[1][i]+=f[1][i-1];up(i,1,3*n) f[2][i]=f[1][i-1]-(i-n-1>=0?f[1][i-n-1]:0);int counter=0;up(s,3,3*n) {int val=f[2][s];if(counter+val>=rk) { up(i,1,n) {int l=max(1ll,s-i-n);int r=min(n,s-i-1);if(l<=r) {if(counter+r-l+1>=rk) {up(j,1,n) {if(1<=s-i-j&&s-i-j<=n) {if(++counter==rk) {cout << i << ' ' << j << ' ' << s-i-j << '\n';return 0;}}}}counter+=r-l+1;}}} counter+=val;}return 0;
}
2-B 机器人 (robot.cpp)
怎么有人下发错误的 statement，谋害本可使爆零，以及这个原题“阻碍关系具有传递性”想何出什么样的意味（？
发现 \(n\leq 1000\)，努力去想简单暴力的办法，考虑所有的可能的阻碍对 \((i,j,t)\) 表示 \(i\) 可能在 \(t\) 时刻阻碍 \(j\)，然后去顺次考虑每一个点对生不生效。因为题目给了一些互不相等所以不用去纠边角情况。发现只要动态维护 \(u\) 有没有被阻碍、以及被阻碍到哪个地方就能判断生效情况以及更新阻碍情况，不尽之处皆是一些简单分讨（？
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_backusing namespace std;const int N=1005, M=1000005;int n, m, x[N], y[N], tag[N], in[N], Ans[N];
vector<int> to[N];
char opt[N];
struct node {int i, j, t;bool operator<(const node &rhs) const { return t<rhs.t; }
} p[M];void dfs(int x) {for(int y:to[x]) dfs(y), Ans[x]+=Ans[y]+1;
}signed main() {freopen("robot.in","r",stdin);freopen("robot.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n;up(i,1,n) cin >> opt[i] >> x[i] >> y[i];up(i,1,n) {if(opt[i]!='N') continue;up(j,1,n) if(opt[j]=='E') {if(x[j]>x[i]||y[j]<y[i]) continue;int ti=y[j]-y[i], tj=x[i]-x[j];if(ti==tj) continue;if(ti<tj) p[++m]=(node){i,j,tj};if(tj<ti) p[++m]=(node){j,i,ti};}}sort(p+1,p+1+m);up(u,1,m) {int i=p[u].i, j=p[u].j;
// cout << "breat " << i << ' ' << j << '\n';if(!tag[j]&&(!tag[i]||opt[i]=='N'&&y[j]<=y[i]+tag[i]||opt[i]=='E'&&x[j]<=x[i]+tag[i])) { tag[j]=p[u].t, to[i].pb(j), ++in[j];}}up(i,1,n) if(!in[i]) dfs(i);up(i,1,n) cout << Ans[i] << '\n';return 0;
}
2-C 总统大选 (election.cpp)
大样例全过挂分的来了。