2024 Jiangsu Collegiate Programming Contest

news/2024/9/23 17:25:46

Preface

这场由于是学长们出的题，在5.5就作为验题队伍VP了一遍

本来验题场一般是三人三机火速开题的，但由于那天徐神没带电脑，索性就三人一机当作训练来打

最后经典被队友带飞，4h8题后和NJU的WF银牌队只差一题，然后最后1h我冲刺H题失败，耻辱下机吃花雕

A. Two's Company but Three's Trumpery

防AK的神秘图论讨论题，鉴定为先吃饭吧

B. Area of the Devil

唉几何题，被徐神看一眼秒杀了，然后祁神上去随便搓了下就过了

我们队的写法是咋拆分面积的说实话我也记不清了，反正我划划水就过了

#include<bits/stdc++.h>
using namespace std;
using LD = long double;
const LD PI = acos(-1.0L);struct Pt{LD x, y;Pt operator-(const Pt &b)const{return Pt{x-b.x, y-b.y};};Pt operator+(const Pt &b)const{return Pt{x+b.x, y+b.y};};Pt operator*(const LD &b)const{return Pt{x*b, y*b};};	LD crs(const Pt &b)const{return x*b.y-y*b.x;}
};
LD cross(const Pt &p, const Pt &a, const Pt &b){return (a-p).crs(b-p);
}Pt pt_l_l(const Pt &p1, const Pt &v1, const Pt &p2, const Pt &v2){return p1 + v1*(v2.crs(p1-p2)/v1.crs(v2));
}
Pt pt_seg_seg(const Pt &p1, const Pt &p2, const Pt &p3, const Pt &p4){return pt_l_l(p1, p2-p1, p3, p4-p3);	
}int t, r, thi[5][2];
Pt pt[5][2];signed main(){ios::sync_with_stdio(0); cin.tie(0);cout << setiosflags(ios::fixed) << setprecision(9);cin >> t;while (t--){cin >> r;for (int p=0; p<2; ++p){for (int i=0; i<5; ++i){cin >> thi[i][p];pt[i][p] = Pt{r*cos(PI*thi[i][p]/180), r*sin(PI*thi[i][p]/180)};	}}LD ans = 0;for (int i=0; i<5; ++i){ans += 0.5L*pt[i][0].crs(pt[i][1]);ans += 0.5L*pt[i][1].crs(pt[(i+1)%5][0]);ans += 0.5L*(1.0L*r*r*(thi[i][1]-thi[i][0])/180*PI - pt[i][0].crs(pt[i][1]));	Pt p = pt_seg_seg(pt[i][1], pt[(i+2)%5][0], pt[(i+1)%5][1], pt[(i+3)%5][0]);ans -= abs(0.5L*cross(p, pt[(i+1)%5][1], pt[(i+2)%5][0]));}cout << ans << '\n';}return 0;	
}

C. Radio Direction Finding

徐神开场直接开的这个题，然后问候了出题人很久后找到一个分6种Case讨论的做法

然而因为我根本不知道这题题意，又只能扔队友代码了

#include <bits/stdc++.h>int n;inline int norm(int a) {a -= 1;a %= n;if(a < 0) a += n;return a + 1;
}int query(int a) {std::cout << "? " << norm(a) << std::endl;int res; std::cin >> res;return res;
}void answer(int a, int b) {std::cout << "! " << norm(a) << ' ' << norm(b) << std::endl;return ;
}void work() {std::cin >> n;int q1 = query(1), q2 = query(2);if(q1 == q2) {int l = 1, r = q1, mid;while(l < r) {int mid = (l + r + 1) >> 1;if(query(1 + mid) == q1) l = mid;else                     r = mid - 1;}l += 1;if(q1 <= n / 2) {answer(l - q1, l);} else {int d = n - q1;int x = l + (n - d - d + 1) / 2;int y = x + d;answer(x, y);}} elseif(q1 - q2 == 1) {int d = n - q1;int x = 2 + (q2 - d) / 2;int y = x + d;answer(x, y);} elseif(q1 - q2 == -1) {int d = n - q2;int x = 1 - (q1 - d) / 2;int y = x - d;answer(x, y);} else if(q1 - q2 == 2) {int d = query(1 + q1 / 2);int x = 1 + (q1 - d) / 2;int y = x + d;answer(x, y);} elseif(q1 - q2 == -2) {int d = query(2 - q2 / 2);int x = 2 - (q2 - d) / 2;int y = x - d;answer(x, y);}return ;
}int main() {std::ios::sync_with_stdio(false);int T; std::cin >> T; while(T--) work();return 0;
}

D. City Bloxx

很有意思的构造题，话说为什么祁神和徐神都玩过这个造房子的小游戏但我完全没有印象

比赛的时候其实已经搞出来了一个理论上可行的构造方法了，但由于一些细节问题（以及机子被我占着写shi了）所以没来得及写

祁神赛后好像把这题补掉了来着

E. Divide

据说有一个\(\log\)的优秀做法，但这个时间和空间限制不写两个\(\log\)真是可惜了

首先不难发现一个数操作\(\log\)次后就会变成\(0\)，因此我们把每个位置上的数以及其操作过后所有能得到的数看作一个可重集

此时的询问l r k等价于询问\([l,r]\)的所有可重集的并集中，排名第\(k+1\)大的数是什么

可以直接用主席树来大力维护上述问题，时空复杂度均为\(O(n\log^2 n)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,q,c[N],x,l,r,k,rt[N];
class Segment_Tree
{private:struct segment{int ls,rs,sz;}node[N*400]; int tot;public:#define TN CI l=1,CI r=100000#define LS l,mid#define RS mid+1,rinline void	insert(CI lst,int& now,CI pos,TN){node[now=++tot]=node[lst]; ++node[now].sz;if (l==r) return; int mid=l+r>>1;if (pos<=mid) insert(node[lst].ls,node[now].ls,pos,LS);else insert(node[lst].rs,node[now].rs,pos,RS);}inline int query(CI x,CI y,CI rk,TN){if (l==r) return l; int mid=l+r>>1;int szr=node[node[y].rs].sz-node[node[x].rs].sz;if (rk<=szr) return query(node[x].rs,node[y].rs,rk,RS);else return query(node[x].ls,node[y].ls,rk-szr,LS);}#undef TN#undef LS#undef RS
}SEG;
int main()
{RI i; for (scanf("%d%d",&n,&q),i=1;i<=n;++i){scanf("%d",&x); if (x==0) { rt[i]=rt[i-1]; c[i]=c[i-1]; continue; }SEG.insert(rt[i-1],rt[i],x); c[i]=1; x>>=1; int lst=rt[i];while (x) SEG.insert(lst,rt[i],x),lst=rt[i],++c[i],x>>=1;c[i]+=c[i-1];}for (i=1;i<=q;++i){scanf("%d%d%d",&l,&r,&k); ++k;if (k>c[r]-c[l-1]) { puts("0"); continue; }printf("%d\n",SEG.query(rt[l-1],rt[r],k));}return 0;
}

F. Download Speed Monitor

签到模拟题，验题时输出的要求好像时截断两位小数来着，但好像因为会有精度误差啥的后面改成了保留六位小数了

代码还是验题时的版本，反正大差不差

#include<cstdio>
#include<iostream>
#include<cmath>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,k,a[N],pfx[N];
signed main()
{RI i; for (scanf("%lld%lld",&n,&k),i=1;i<=n;++i)scanf("%lld",&a[i]),pfx[i]=pfx[i-1]+a[i];for (i=k;i<=n;++i){int sum=pfx[i]-pfx[i-k];if (sum<1024LL*k){int tmp=floor((long double)(sum)*100/k);printf("%lld.",tmp/100); tmp%=100;printf("%lld%lld KiBps\n",tmp/10,tmp%10);} else{int tmp=floor((long double)(sum)*100/k/1024);printf("%lld.",tmp/100); tmp%=100;printf("%lld%lld MiBps\n",tmp/10,tmp%10);}}return 0;
}

G. Download Time Monitor

又是签到模拟题，但有人因为用cin读入double太慢导致TLE了好几发，我不好评价

做法本身没啥好说的，注意要用int读入再转成double操作

#include<bits/stdc++.h>
using namespace std;
using LD = double;
#define Tp template <typename T>
class FileInputOutput
{private:static const int S=1<<21;#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)char Fin[S],*A,*B;public:Tp inline void read(T& x){x=0; char ch; while (!isdigit(ch=tc()));while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}#undef tc
}F;
int tt;
signed main(){//freopen("1.out", "r", stdin);//freopen("1.in", "w", stdout);cout << setiosflags(ios::fixed) << setprecision(9);cin >> tt;while (tt--){int B_, t1_, a1_, t2_, a2_;F.read(B_); F.read(t1_); F.read(a1_); F.read(t2_); F.read(a2_);LD B=B_, t1=t1_, a1=a1_, t2=t2_, a2=a2_;LD ans1=0.0L, ans2=0.0L;if (1.0L*a1/B + t1 <= t2){ans1 = 1.0L*a1/B;ans2 = 1.0L*a2/B;}else{ans1 = t2 - t1;a1 -= (t2-t1)*B;LD val = min(2.0L*a1/B, 2.0L*a2/B);ans1 += val;ans2 += val;a1 -= val*B/2;a2 -= val*B/2;ans1 += a1/B;ans2 += a2/B;}cout << ans1 << ' ' << ans2 << '\n';}return 0;	
}

H. Real Estate Is All Around

唉这题比赛的时候徐神一直跟我说是个Flow，但我就是想去写DP，最后看Tutorial发现两种都行

但比赛时以为单组数据\(O(n^3)\)的做法会T掉（实际上跑不满就不会），所以在已经讨论出了所有关键性质的情况下没去写显而易见的\(O(n^3)\)DP，而是去写了一个神秘的带悔贪心，成功把自己送走

这题的几个关键的观察就是对于小红和小蓝，我们只会把它们要卖的房子交给它们，而多余的房子全都都扔给小绿是最优的

而小绿又每次卖售价最高的房子，这就导致每个房子要么在交给某个人后可以确定一定会售出，要么就相当于直接扔掉了这个房子

考虑直接使用DP求解，不妨设\(f_{i,x,y,z}\)表示已经处理了前\(i\)个操作，每个人手上存有的房子数分别为\(x,y,z\)的最大收益，转移十分trivial，但复杂度是\(O(n^4)\)的

考虑如何优化，显然小红和小蓝收取的中介费和房子本身的售价没有任何关系，因此我们可以把交给他们两个的房子合并到一起去

区别是在遇到第二类事件时，如果选择从他们俩那拿出两套房子的话，就需要额外支付\(1\)的代价，否则我们总是贪心地把房子给小蓝

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=205,INF=1e9;
int t,n,tp,x,f[N][N][N];
int main()
{for (scanf("%d",&t);t;--t){RI i,j,k; scanf("%d",&n);for (i=0;i<=n;++i) for (j=0;j<=n;++j) for (k=0;k<=n;++k) f[i][j][k]=-INF;for (f[0][0][0]=i=0;i<n;++i){if (scanf("%d",&tp),tp==1){for (scanf("%d",&x),j=0;j<=i;++j) for (k=0;j+k<=i;++k)if (f[i][j][k]!=-INF){f[i+1][j][k]=max(f[i+1][j][k],f[i][j][k]);f[i+1][j+1][k]=max(f[i+1][j+1][k],f[i][j][k]+x-(x+9)/10);f[i+1][j][k+1]=max(f[i+1][j][k+1],f[i][j][k]+x);}} else{for (j=0;j<=i;++j) for (k=0;j+k<=i;++k)if (f[i][j][k]!=-INF){f[i+1][max(0,j-1)][max(0,k-1)]=max(f[i+1][max(0,j-1)][max(0,k-1)],f[i][j][k]);f[i+1][max(0,j-1)][max(0,k-2)]=max(f[i+1][max(0,j-1)][max(0,k-2)],f[i][j][k]-1);}}}printf("%d\n",f[n][0][0]);}return 0;
}

网络流的做法也比较经典，但比赛的时候没仔细想，赛后看了眼Tutorial的建图感觉还是挺经典的

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=205,INF=1e9;
int T,n,tp,idx,sum,x;
namespace MinCost_MaxFlow
{const int NN=1005;struct edge{int to,nxt,v,c;}e[1000005]; int head[NN],cur[NN],s,t,cnt=1,dis[NN]; bool vis[NN];inline void addedge(CI x,CI y,CI v,CI c){//printf("%d %d %d %d\n",x,y,v,c);e[++cnt]=(edge){y,head[x],v,c}; head[x]=cnt;e[++cnt]=(edge){x,head[y],0,-c}; head[y]=cnt;}#define to e[i].toinline bool SPFA(CI s,CI t){RI i; for (i=1;i<=idx;++i) dis[i]=INF; dis[s]=0;queue <int> q=queue <int>(); q.push(s);while (!q.empty()){int now=q.front(); q.pop(); vis[now]=0;for (i=head[now];i;i=e[i].nxt)if (e[i].v&&dis[now]+e[i].c<dis[to])if (dis[to]=dis[now]+e[i].c,!vis[to]) q.push(to),vis[to]=1;}return dis[t]!=INF;}inline int DFS(CI now,CI tar,int tmp,int& flow,int& cost){if (now==tar) return flow+=tmp,tmp;int ret=0; vis[now]=1;for (RI& i=cur[now];i&&dis;i=e[i].nxt)if (!vis[to]&&e[i].v&&dis[to]==dis[now]+e[i].c){int dist=DFS(to,tar,min(tmp-ret,e[i].v),flow,cost);ret+=dist; e[i].v-=dist; e[i^1].v+=dist; cost+=dist*e[i].c;if (ret==tmp) break;}vis[now]=0; return ret;}#undef toinline void Dinic(CI s,CI t,int& flow,int& cost){flow=cost=0; while (SPFA(s,t)) memcpy(cur,head,idx+1<<2),DFS(s,t,INF,flow,cost);}inline void clear(void){for (RI i=1;i<=idx;++i) head[i]=0; cnt=1;}
};
using namespace MinCost_MaxFlow;
int main()
{for (scanf("%d",&T);T;--T){RI i,j; scanf("%d",&n); s=1; t=2; sum=0;auto ID=[&](CI x,CI y){return (x-1)*3+y+2;};for (idx=ID(n,3),i=1;i<=n;++i){if (i!=n){for (j=1;j<=3;++j) addedge(ID(i,j),ID(i+1,j),INF,0);}if (scanf("%d",&tp),tp==1){scanf("%d",&x); sum+=x;++idx; addedge(s,idx,1,0);addedge(idx,ID(i,1),1,1);addedge(idx,ID(i,2),1,(x+9)/10);addedge(idx,ID(i,3),1,0);addedge(idx,t,1,x);} else{for (j=1;j<=3;++j) addedge(ID(i,j),t,1,0);}}int flow,cost; Dinic(s,t,flow,cost);printf("%d\n",sum-cost); clear();}return 0;
}

I. Integer Reaction

很套路的题，最小值最大一眼二分答案\(lim\)，考虑如何检验

用两个multiset分别存储当前两种颜色还未发生反应的集合，对于一个新元素\(x\)：

若不存在与它颜色相反的元素，则将其加入它对应颜色的multiset中
若存在与它颜色相反的元素，则尝试找到最小的\(y\)满足\(x+y\ge lim\)，即等价于查询\(lim-x\)的后继

总复杂度\(O(n\log n\log a_i)\)

#include<cstdio>
#include<iostream>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,a[N],c[N];
inline bool check(CI x)
{multiset <int> s[2];for (RI i=1;i<=n;++i){if (s[c[i]^1].empty()){s[c[i]].insert(a[i]); continue;}auto it=s[c[i]^1].lower_bound(x-a[i]);if (it==s[c[i]^1].end()) return 0;s[c[i]^1].erase(it);}return 1;
}
int main()
{RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);for (i=1;i<=n;++i) scanf("%d",&c[i]);int l=1,r=2e8,mid,ret; while (l<=r)if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;printf("%d\n",ret);return 0;
}

J. Tile Covering

刚开始硬上了个按行状压的东西，然后发现状态数爆炸了只能跑\(15\)左右

大致思路就是状压每行的状态，不难发现如果有连着的一段\(1\)（长度大于等于\(2\)），那么这里一定是横着放的一块骨牌，则下面一行这些位置都必须放\(0\)

否则对于单独的\(1\)，我们默认其是竖着放的，这样下一行还能放\(1\)，然后爆搜一下转移状态，然后就寄了

后面看知乎好像有高手用这种写法过了，不过可能还要在加个高位前缀和优化之类的，但也懒得去补了

#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=(1<<18)+5;
int n,m,a[20][20],c[20],t[20],cs[20],f[20][N],g[20][N];
vector <int> vec[N],valid[20];
inline void DFS1(vector <int>& v,CI cur,CI mask)
{if (cur>=m) return v.push_back(mask);if (t[cur]!=-1) return cs[cur]=t[cur],DFS1(v,cur+1,mask);if (cur>0&&c[cur-1]==1&&cs[cur-1]==1)return cs[cur]=0,DFS1(v,cur+1,mask);if (cur>0&&cs[cur-1]==1&&c[cur]==1)return cs[cur]=0,DFS1(v,cur+1,mask);cs[cur]=0; DFS1(v,cur+1,mask);cs[cur]=1; DFS1(v,cur+1,mask|(1<<cur));
}
inline void DFS2(CI rid,CI cur,CI mask,CI sum)
{if (cur>=m) return (void)(valid[rid].push_back(mask),g[rid][mask]=sum);if (a[rid][cur]<=0) return DFS2(rid,cur+1,mask,sum);DFS2(rid,cur+1,mask,sum);DFS2(rid,cur+1,mask|(1<<cur),sum+a[rid][cur]);
}
int main()
{RI i,j; for (scanf("%d%d",&n,&m),i=0;i<n;++i)for (j=0;j<m;++j) scanf("%d",&a[i][j]);for (i=0;i<(1<<m);++i){for (j=0;j<m;++j) c[j]=(i>>j)&1,t[j]=-1;for (j=0;j<m;++j)if (c[j]&&((j>0&&c[j-1])||(j<m-1&&c[j+1]))) t[j]=0;DFS1(vec[i],0,0);}/*int all=0; for (i=0;i<(1<<m);++i){all+=vec[i].size();for (auto x:vec[i]) printf("%d %d\n",i,x);}printf("%d\n",all);*/memset(g,-1,sizeof(g));for (i=0;i<n;++i) DFS2(i,0,0,0);memset(f,-1,sizeof(f));for (auto mask:valid[0]) f[0][mask]=g[0][mask];for (i=0;i<n-1;++i)for (auto mask:valid[i]) if (~f[i][mask])for (auto nxt:vec[mask]) if (~g[i+1][nxt])f[i+1][nxt]=max(f[i+1][nxt],f[i][mask]+g[i+1][nxt]);int ans=0; for (auto mask:valid[n-1]) ans=max(ans,f[n-1][mask]);return printf("%d",ans),0;
}

后面发现了更本质的限制，其实就是放棋子的位置不能出现拐弯

那么可以用插头DP，设\(f_{i,j,mask}\)表示从上到下，从左到右处理到\((i,j)\)位置，此时的轮廓线状压状态为\(mask\)时的最优权值和

和常规的插头DP的区别就是要多记录一个\((i-1,j)\)的状态，其它的基本没什么区别

总复杂度\(O(nm\times 2^m)\)

#include <bits/stdc++.h>int a[20][20];
int dp_base[2][2][1 << 18];
auto dp1 = dp_base[0], dp2 = dp_base[1];void chkmx(int &a, const int b) {if(b > a) a = b;
}int main() {memset(dp_base, 0x80, sizeof(dp_base));// std::cout << sizeof(dp_base) / 1024.L / 1024.L << char(10);int n, m;std::cin >> n >> m;for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) std::cin >> a[i][j];dp1[0][0] = 0;const int U = (1 << m) - 1;for(int i = 1; i <= n; ++i) for(int j = 0; j < m; ++j) {memset(dp2, 0x80, sizeof(dp_base[0]));for(int b = 0; b < 2; ++b) for(int s = 0; s < (1 << m); ++s) {// for dp1 at x, yconst int x = i, y = j;const int cur = (s >> y) & 1;const int pre = (y == 0 ? 0 : ((s >> y - 1) & 1));const int nxt = (s >> y + 1) & 1;const int nb = (y == m - 1 ? 0 : cur);chkmx(dp2[nb][s & (U ^ (1 << y))], dp1[b][s]);if(pre && b || b && cur || cur && nxt || cur && pre) continue;chkmx(dp2[nb][s | (1 << y)], dp1[b][s] + a[x][y + 1]);}std::swap(dp1, dp2);
//		for(int b = 0; b < 2; ++b) for(int s = 0; s < (1 << m); ++s)
//			std::cerr << "dp[" << i + (j == m - 1) << "][" << (j + 1) % m << "]["
//			<< b << "][" << s << "] = " << dp1[b][s] << char(10);}int ans = 0;for(int b = 0; b < 2; ++b) for(int s = 0; s < (1 << m); ++s)// std::cerr << "dp[" << b << "][" << s << "] = " << dp1[b][s] << char(10),chkmx(ans, dp1[b][s]);std::cout << ans << char(10);return 0;
}/*
4 4
-1 2 1 -2
3 2 0 -2
-3 -2 0 3
2 3 0 1
*/

K. Number Deletion Game

被祁神一眼秒了的博弈题，不难发现胜负仅与最大数出现次数的奇偶性有关，证明可以采用归纳法

#include<bits/stdc++.h>
using namespace std;int n;
signed main(){ios::sync_with_stdio(0); cin.tie(0);cin >> n;int mx=0, cnt=0;for (int i=1; i<=n; ++i){int a; cin >> a;if (a>mx) mx=a, cnt=1;else if (a==mx) ++cnt;}cout << (cnt%2==1 ? "Alice\n" : "Bob\n");return 0;	
}