CSP 2023 游记
优先看https://www.luogu.com.cn/paste/xegs7srz
CSP终于来了，本想着这次pj 300+，tg 2=。看来要AFO了……
-
7：40
到了耀华考场，没想到已经有很多人来了，@Frank08，@2020luke，@mayingdi520 都来了。。他们好像二十分就来了。过了一会，@2023FJZ来了，在他的外套里面穿着耀华的衣服：耀华外星人。张老师也来了，送了我们进去。 -
8：30
终于开考了，我这个试室友 @Frank08 和 @2023FJZ。
第一题乍一看：不会
再一看：好简单，一直÷3就可以了。 -
8：50
T1悠闲地过样例，顺便准备了一些文件的位置。#include <bits/stdc++.h> using namespace std; int n,x; int res=0; int ans=0; int main(){ freopen("apple.in","r",stdin); freopen("apple.out","w",stdout); scanf("%d",&n); x=n;int cnt=0; while(x){ if(x % 3 == 1 && !ans) ans=res+1; if(x%3==0){ x -= x / 3; }else{ x -= x / 3 + 1; }res++; } printf("%d %d",res,ans); return 0; } -
9：20
T2也很简单，贪心即可，过阳历，走人。#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5+5; ll n,d; ll v[N],a[N]; ll minn = 1e9;//随时维护目前最小值 ll cnt =0 ;//目前可以走到多少 ll res=0;//累计 ll x=0; ll ans=0; int main(){ freopen("road.in","r",stdin); freopen("road.out","w",stdout); cin >> n >> d; for(int i = 1;i <= n-1;i++) scanf("%lld",&v[i]); for(int i = 1;i <= n;i++) scanf("%lld",&a[i]); for(int i =1;i <= n-1;i++){ minn = min(minn,a[i]); res+=v[i]; x = (((res-cnt) % d == 0)?((res-cnt)/d):((res-cnt)/d+1)); // cout<<res<<" "<<cnt<<" "<<x<<endl; ans+=1ll*x*minn; cnt+=x*d; } printf("%lld",ans); return 0; }T3这题面也太复杂了吧，看都看不懂捏，花了10分钟终于看完了，喘了一口气，发现不就是解一元二次方程嘛，这出题人还怪友善的，把模拟过程告诉我们了。
-
11：00
T3终于过阳历了，一百多行，大概可以过了。#include <bits/stdc++.h> using namespace std; int t,m; int a,b,c; bool wqpf(double x){ if(int(sqrt(x))*int(sqrt(x)) == x) return true; return false; }void pout(int ox1,int ox2,int y){ int x=(y<0?min(ox1,ox2):max(ox1,ox2)); while(__gcd(x,y) != 1){ int z=__gcd(x,y); x/=z;y/=z; } if(y<0 && x<0){ x=abs(x); y=abs(y); }else if(y<0 || x<0){ x=abs(x); y=abs(y); x=-x; } if(y==1) printf("%d\n",x); else printf("%d/%d\n",x,y); }void pout2(int x,int y){ while(__gcd(x,y) != 1){ int z=__gcd(x,y); x/=z;y/=z; } if(y<0 && x<0){ x=abs(x); y=abs(y); }else if(y<0 || x<0){ x=abs(x); y=abs(y); x=-x; } if(y==1) printf("%d",x); else printf("%d/%d",x,y); } void haj(int a,int b){ if(a%b==0){ a/=b; b=1; int flag=1; while(flag){ // cout<<a<<" "<<b<<endl; flag=0; for(int i = 2;i <= sqrt(a);i++){ if(a % (i*i) ==0 ){ a/=i*i; b*=i; flag=1; break; } } } if(b==1){ printf("sqrt(%d)\n",a); }else{ printf("%d*sqrt(%d)\n",b,a); } }else{ b=sqrt(b); int xb=1; int flag=1; while(flag){ // cout<<a<<" "<<b<<endl; flag=0; for(int i = 2;i <= sqrt(a);i++){ if(a % (i*i) ==0 ){ a/=i*i; xb*=i; flag=1; break; } } } // xb * sqrt(a) / b; while(__gcd(xb,b) != 1){ int z=__gcd(xb,b); xb/=z;b/=z; } if(b<0 && xb<0){ xb=abs(xb); b=abs(b); }else if(b<0 || xb<0){ xb=abs(xb); b=abs(b); xb=-xb; } if(xb!=1){ if(b==1) printf("%d*sqrt(%d)\n",xb,a); else printf("%d*sqrt(%d)/%d\n",xb,a,b); }else{ if(b==1) printf("sqrt(%d)\n",a); else printf("sqrt(%d)/%d\n",a,b); } } } void run(int a,int b,int c){ if(b){ pout2(-b,2*a); printf("+"); } haj(b*b-4*a*c,4*a*a); } int main(){ freopen("uqe.in","r",stdin); freopen("uqe.out","w",stdout); scanf("%d%d",&t,&m); for(int i = 1;i <= t;i++){ scanf("%d%d%d",&a,&b,&c); // cout<<"---"<<i<<endl; double deltaa = double(b*b)-4.0*a*c; if(deltaa < 0){ printf("NO\n"); }else if(wqpf(deltaa)){ // cout<<deltaa<<endl; // cout<<sqrt(deltaa)<<endl; pout(-b+sqrt(deltaa),-b-sqrt(deltaa),2*a); }else{ run(a,b,c); } } return 0; } /* 1 1000 -2 12 270 15 */很兴奋，去上个厕所放松放松。耀华的厕所好豪华又好破旧啊。
然后开始磕T4，发现用DP可以解决，直接枚举 \(dp_{i,j}\) 表示第 \(i\) 个点 mod \(k==j\) 。
只想到用个BFS来转移，感觉时间复杂度要炸到飞起，小样例过掉，大样例输出-1，调了半天不搞了
#include <bits/stdc++.h> using namespace std; const int N = 1E4+5; int n,m,k; vector<pair<int,int> > mp[N]; int dp[N][105]; int main(){ freopen("bus.in","r",stdin); freopen("bus.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for(int i = 1;i <= n;i++){ int u,v,a; scanf("%d%d%d",&u,&v,&a); mp[u].push_back({v,a}); } memset(dp,0x3f,sizeof dp); dp[1][0]=0; queue<pair<int,int> > q; for(int i = k;i <= 2e6+5;i+=k){ q.push({i,1}); } while(!q.empty()){ pair<int,int> f=q.front(); q.pop(); for(auto it:mp[f.second]){ if(it.second > f.first) continue; dp[it.first][(f.first+1) % k] = min(dp[it.first][(f.first+1) % k],dp[f.second][(f.first) % k]); q.push({f.first+1,it.first}); } } printf("%d",(dp[n][0]==0x3f3f3f3f)?-1:(dp[n][0])); return 0; } -
中午回家睡了但没完全睡
Syx打电话过来，说他AK了，他好像很兴奋。他T4用了dij来维护，几乎跟我想到一块去了，其实也就是bfs，但是他的方法是不够的时候一直+k，我是枚举起点+多少k，所以我的时间复杂度要上天，他的就是正解。
感觉状态很不好，明明T4都要想出来了，还是挂。 -
13：40 到达考场，几个同学来了，好像都说上午300+，看来300是大众分，还有T3没调出来的（。
- 14：30 开考，T1不是很简单吗，暴力枚举就行了呢，不会是我看错了吧，历年tgT1还是有难度的(绿~蓝)，今年不可能那么简单，于是我反复读了5遍，确认自己没想错，开写。
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int s[10];
int b[10];
int n;
int cha(int x,int y){
if(x>=y)return x-y;
return x+10-y;
}
int main(){
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
scanf("%d",&n);
for(int i =1;i <= n;i++){
for(int j = 1 ;j<= 5;j++){
scanf("%d",&a[i][j]);
}
}
int ans=0;
int cnt=0;
for(s[1] = 0;s[1] <= 9;s[1]++){
for(s[2] = 0;s[2] <= 9;s[2]++){
for(s[3] = 0;s[3] <= 9;s[3]++){
for(s[4] = 0;s[4] <= 9;s[4]++){
for(s[5] = 0;s[5] <= 9;s[5]++){
int flag=1;
for(int i =1;i <= n&&flag;i++){
for(int j = 1;j <= 5;j++){
b[j]=cha(a[i][j],s[j]);
}
int sum=0;
for(int i = 1;i <= 5;i++){
if(b[i]) sum++;
}
if(sum>=3 || sum==0){
flag=0;
break;
}
if(sum==2){
flag=0;
for(int i = 2;i <= 5;i++){
if(b[i]==b[i-1]&&b[i]&&b[i-1]) {
flag=1;
break;
}
}
}
}
if(flag==1) {
ans++;
}
}
}
}
}
}
cout<<ans;
return 0;
}
优雅的七层for
- 15：00 T1过样例，理论时间复杂度不会超过 \(10^6\)，没问题了。剩下的开始骗分。T2一眼看就是区间DP，但一看数据范围，\(O(n \log n)\) 都过不去，自己手推了一下，仔细想能否有 \(n^2\) 的时间做出来，因为如果那样就可以拿到50分，发现不会，于是 \(O(n^3)\) 的时间复杂度区间DP过掉了前两个样例，其他TLE了。。
#include <bits/stdc++.h>
using namespace std;
const int N = 8005;
int n;
string c;
bool dp[N][N];
long long ans=0;
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
cin >> c;
c=' '+c;
for(int i = 2;i <= n;i++){
if(c[i]==c[i-1]) dp[i-1][i]=1;
}
for(int len = 2;len <= n;len += 2){
for(int l = 1;l+len-1<=n;l++){
int r=l+len-1;
for(int k = l;k<r;k++){
dp[l][r]|=dp[l][k] && dp[k+1][r];
}
dp[l][r] |= (c[l]==c[r] && dp[l+1][r-1]);
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
// if(dp[i][j])cout<<i<<" "<<j<<"\n";
ans+=dp[i][j];
}
}printf("%lld",ans);
return 0;
}
- 忘记是几点了，开始磕T3，发现，就是大模拟？然后我是个自以为是的家伙，试图写正解，发现快吐了，接近100行时，放弃了，决定拿25分（特殊情况A），搞定，样例1的那一部分过掉了。
这洛谷blog md渲染有问题呀，一贴上来代码就乱码了 - 还剩两小时，满满磕T4，然后发现，T4想多拿5分都不让，于是想到了一条链的那种情况，10分，于是我用二分来模拟，那就是 \(O(n \log n)\) 的解法，貌似也行得通。然后就写啊写，写啊写。一个小时过去了，却几乎没写一样，终于终于，在我首推的数据中，他终于成功了。太兴奋了，以为是100+35+25+10，要是170还不错呢！
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1E5+5;
ll n;
ll a[N];
ll b[N],c[N];
vector<int> mp[N];
bool chelin(ll mid){
for(int i = 1;i <= n;i++){
ll res=0;
if(c[i]>=0ll){
// cout<<'x';
res=(mid-i+1) * b[i] + 1ll*(mid+i)*(mid-i+1)/2*c[i];
// cout<<1ll*(mid-i+1) * b[i]<<" "<<1ll*((b[i]/(-c[i]))-1+i)*((b[i]/(-c[i]))-1-i+1)/2<<" "<<mid-(b[i]/(-c[i]))+1<<endl;
}else{
// cout<<'y';
res=(mid-i+1) * b[i] + c[i]*(1ll*((b[i]/(-c[i]))-1+i)*((b[i]/(-c[i]))-1-i+1)/2 )- ((b[i]-1)*(mid-(b[i]/(-c[i]))+1));
}
// cout<<mid<<" "<<i<<" "<<res<<endl;
if(res<a[i]){
// cout<<"f\n";
return false;
}
}
// cout<<"t\n";
return true;
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin >> n;
for(int i = 1;i <= n;i++){
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
}for(int i = 1;i <= n-1;i++){
int u,v;
scanf("%lld%lld",&u,&v);
mp[u].push_back(v);
}
//??
ll l=n,r=1e9,mid;
while(l<r){
mid=(l+r)>>1;
if(chelin(mid)) r=mid;
else l=mid+1;
}cout<<l;
return 0;
}
就这个二分快把我搞死了（结果后面一分没拿）
此时剩下半小时，不知道噩梦才刚刚开始，我兴致勃勃的回去检查T3，然后试了一下样例2的特殊部分能不能过，结果发现竟然错了！！发现了一个很明显的错误，改完后，喘了口气，想到：幸好我找出错误来了，结果发现就是这样样例1也过不去？！！？！！我差点崩溃了，还有10分钟，25分，根本没有状态去思考，然后就瞪眼法DeBug，剩下5秒还是看不出来，freopen打开，寄了，两个样例没过，只能遗憾的走出考场。。（bei，稳了ziyistudy，他说T2看出来是区间DP拿35，但不会写（乐
出了考场拿到手机，发现上午pj的小图灵估分出了，怎么才215？？
第二题挂成15！
回到家后发现：
小图灵：100+15+100+0=215
洛谷：100+65+100+10=275
信友队：100+60+100+0=260
第二天早上找了Syx，原来我是个傻子（大雾，你油都是够的，你加什么啊？？改完后瞬间AC！
到目前为止，下午tg的成绩是：
100+35+0+0
洛谷：100+35+0+0
云斗：100+35+0+5
小图灵：100+35+0+0
看来也就135了，拿一等的希望不超过5%
为什么最后一题会挂成0分啊？？
没事前两题幸好没有挂分，看到SyxT1挂成70，我有点开心，（他目前：70+35+？+0）然后@2023FJZ貌似是100+25+？+0，@chenweizhen 是40+30。
我貌似得到了一点安慰但不多。。
明年再来，拿个7级勾！！！
https://www.luogu.com.cn/paste/xegs7srz 剪切版的md就没问题
