\(B. Marbles\)
如果是 \(Nim\) 博弈，题目应该改成到转移所有石子。显然要转化到将所有石子转移到 \((1,2)\) 或者 \((2,1)\) ，特判无需到达这两个点的必败态，对其他点使用 \(Nim\) 博弈判断胜负态。
int sg[N][N],vis[N];
void init(){
for(int i=1;i<=100;i++){
for(int j=1;j<=100;j++){
if(i==j)continue;
memset(vis,0,sizeof vis);
for(int k=1;k<i;k++){
if(k==j)continue;
vis[sg[k][j]]=1;
}
for(int k=1;k<j;k++){
if(k==i)continue;
vis[sg[i][k]]=1;
}
for(int k=1;k<min(i,j);k++){
vis[sg[i-k][j-k]]=1;
}
for(int k=0;;k++){
if(vis[k]==0){
sg[i][j]=k;
break;
}
}
}
}
}
void solve(){
int n=read(),fl=0,ans=0;
for(int i=1;i<=n;i++){
int x=read(),y=read();
if(x==y||x==0||y==0){
fl=1;
}
ans^=sg[x][y];
}
puts(ans||fl?"Y":"N");
//puts(ans>0?"Yes":"No");
}
\(C. Pizza Cutter\)
每个横线与竖线都会相交，产生 \((横线数量+1) * (竖线数量+1)\) 的披萨。然后考虑横线与横线相交，自然的能想到一对逆序对会多构成一个披萨块，然后按照一边的大小顺序对另一边排列，然后求逆序对就可以了，竖线同理。
int tr[N],tmp[N],c[N];
struct node{
int a,b;
friend bool operator<(const node&a,const node&b){
if(a.a==b.a)return a.b<b.b;
return a.a<b.a;
}
}p[N],q[N];
int lowbit(int x){
return x & -x;
}
void add(int x,int n){
for (int i = x; i <= n; i += lowbit(i))
tr[i] ++;
}
int query(int x){
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
int get_n(int a[],int n){
memset(tr, 0, sizeof tr);
int res = 0;
for (int i = 1; i <= n; i ++ ){
res += query(n) - query(a[i] - 1);
add(a[i],n);
}
return res;
}
void solve(){
int n=read(),m=read();
int h=read(),v=read();
for(int i=1;i<=h;i++){
p[i].a=read();
p[i].b=read();
}
sort(p+1,p+1+h);
for(int i=1;i<=v;i++){
q[i].a=read();
q[i].b=read();
}
sort(q+1,q+1+v);
int ans=0;
for(int i=1;i<=h;i++){
tmp[i]=p[i].b;
}
sort(tmp+1,tmp+1+h);
for(int i=1;i<=h;i++){
c[i]=lower_bound(tmp+1,tmp+1+h,p[i].b)-tmp;
}
ans+=get_n(c,h);
for(int i=1;i<=v;i++){
tmp[i]=q[i].b;
}
sort(tmp+1,tmp+1+v);
for(int i=1;i<=v;i++){
c[i]=lower_bound(tmp+1,tmp+1+v,q[i].b)-tmp;
}
ans+=get_n(c,v);
cout<<ans+(h+1)*(v+1)<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D. Unraveling Monty Hall\)
如果一开始选中了就会选错，一开始选错了就会选对，那么记录有多少次选错了即可。
void solve(){
int n=read(),ans=0;
for(int i=1;i<=n;i++){
int x=read();
if(x==1)continue;
else ans++;
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(E. Enigma\)
暴力枚举每个字符串是否有相同的。
void solve(){
string s,t;
cin>>s>>t;
int ns=s.size();s=' '+s;
int nt=t.size();t=' '+t;
int ans=ns-nt+1;
for(int i=1;i<=ns-nt+1;i++){
for(int j=1;j<=nt;j++){
if(s[i+j-1]==t[j]){
ans--;
break;
}
}
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(F. Music Festival\)
感觉 \(dp\) 很明显，因为 \(n\) 很小，显然状压。将每个演唱的右端点记录，每次从左端点的各个状态转移过来，每次能转移的状态为与当前状态相同的点和当前状态去掉目前的演唱会的状态，其中还要判断一下是否这个状态存在。
vector<array<int,3> >g[86405];
int f[86405][1100];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
int k=read();
for(int j=1;j<=k;j++){
int x=read(),y=read(),w=read();
g[y].push_back((array<int,3>){x,w,i});
}
}
for(int i=1;i<=86400;i++){
for(int j=0;j<(1<<(n));j++){
f[i][j]=f[i-1][j];
for(auto it:g[i]){
int l=it[0],w=it[1],k=it[2]-1;
if(((j>>k)&1)&&(f[l][j-(1<<k)]>0))f[i][j]=max(f[i][j],f[l][j-(1<<k)]+w);
if((((j&(((1<<n)-1)-(1<<k)))==0))||(f[l][(j&(((1<<n)-1)-(1<<k)))]>0))f[i][j]=max(f[i][j],f[l][(j&(((1<<n)-1)-(1<<k)))]+w);
}
}
}
int ans=0;
for(int i=1;i<=86400;i++){
ans=max(ans,f[i][(1<<(n))-1]);
}
if(ans==0)cout<<-1<<'\n';
else cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(G. Gasoline\)
作为网络流的第一题，改出了一个自己的板子。
由于最短时间，二分答案。对于当前二分的时间，显然只有 \(<=x\) 的边才能相连，然后设立源点汇点，跑最大流，看最后是否满流即可。
int st, ed, h[N], idx = 0, d[N],e[N],rk[N];
struct node {
int u, v, ne, w;
}edg[N],G[N];
int p,r,c,sum=0;
void addedge(int u, int v, int w) {
edg[idx].u = u; edg[idx].v = v; edg[idx].ne = h[u];
edg[idx].w = w; h[u] = idx++;
}
int bfs() {
queue<int>q;
memset(rk,0,sizeof rk);
rk[st] = 1;
q.push(st);
while (!q.empty()) {
int tmp = q.front(); q.pop();
for (int i = h[tmp]; i != -1; i = edg[i].ne) {
int to = edg[i].v;
if (rk[to] || edg[i].w <= 0)continue;
rk[to] = rk[tmp] + 1; q.push(to);
}
}
return rk[ed];
}
int dfs(int u, int flow) {
if (u == ed)return flow;
int add = 0;
for (int i = h[u]; i != -1 && add < flow; i = edg[i].ne) {
int v = edg[i].v;
if (rk[v] != rk[u] + 1 || !edg[i].w)continue;
int tmpadd = dfs(v, min(edg[i].w, flow - add));
if (!tmpadd) { rk[v] = -1; continue; }
edg[i].w -= tmpadd; edg[i ^ 1].w += tmpadd;
add += tmpadd;
}
return add;
}
int dinic() {
int ans=0;
while (bfs())ans += dfs(st, inf);
return ans;
}
bool check(int x) {
idx = 0;
memset(edg,0,sizeof edg);
memset(h,-1,sizeof h);
st = 0;
ed = p + r + 2;
for (int i = 1; i <= r; i++)addedge(st, i, e[i]), addedge(i, st, 0);
for (int i = 1; i <= p; i++)addedge(i + r, ed, d[i]), addedge(ed, i + r, 0);
for (int i = 1; i <= c; i++) {
if (x >= G[i].w) {
addedge(G[i].v, G[i].u + r, inf); addedge(G[i].u + r, G[i].v, 0);
}
}
if (dinic() == sum)return true;
return false;
}
int bs1(int l, int r){ //左偏二分
while (l < r){
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
void solve(){
memset(h,-1,sizeof h);
p=read(),r=read(),c=read();
for(int i=1;i<=p;i++){
d[i]=read();
sum+=d[i];
}
for(int i=1;i<=r;i++){
e[i]=read();
}
for(int i=1;i<=c;i++){
G[i].u=read();
G[i].v=read();
G[i].w=read();
}
int ans=bs1(0,10000001);
if(ans==10000001)cout<<-1<<'\n';
else cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(I. Switches\)
显然操作两回合会回到初态，那么模拟两回合是否能完成任务即可。
vector<int>op[N];
void solve(){
int n=read(),m=read();
vector<int>aim(m+1);
int l=read();
for(int i=1;i<=l;i++){
aim[read()]=1;
}
for(int i=1;i<=n;i++){
int x=read();
for(int j=1;j<=x;j++){
op[i].push_back(read());
}
}
for(int i=1;i<=2*n;i++){
int x=(i-1)%n+1;
for(auto y:op[x]){
aim[y]^=1;
}
int ok=1;
for(int j=1;j<=m;j++){
if(aim[j]==1){
ok=0;
break;
}
}
if(ok){
cout<<i<<'\n';
return ;
}
}
cout<<-1<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(K. Kepler\)
将半径按降序排列，用 \(O(n^2)\) 遍历。显然对于大圆，如果与小圆的半径相差 \(50\) 那么显然不会有交集。如果大圆与一个小圆没有交集显然也不会与更小的圆有交集，此时可以 \(break\) ，这样可以让稀疏的地方度过的更快。
struct node{
double x,y;
double r;
friend bool operator<(const node&a,const node&b){
return a.r<b.r;
}
}cir[N];
int check(int x,int y){
return fabs(cir[x].r-cir[y].r)<sqrt(fabs((cir[y].x-cir[x].x)*(cir[y].x-cir[x].x)+(cir[y].y-cir[x].y)*(cir[y].y-cir[x].y)));
}
void solve(){
int n=read();
for(int i=1;i<=n;i++){
cin>>cir[i].x>>cir[i].y>>cir[i].r;
}
sort(cir+1,cir+1+n);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(cir[j].r-cir[i].r>50) break;
ans+=check(i,j)*2;
if(ans>2*n){
cout << "greater\n";
return ;
}
}
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}