训练情况
rk#4
\(100 + 100 + 100 + 70 = 370\)
赛后反思
没什么很严重的失误，只是国庆早八起不来，打到后面时间不够做第四题了QAQ，下次一定早起TAT
A题
开场怎么是CF Div4 原题，显然因为 \(a,b,c,d\) 互不相同，最后切出来的结果只有三块或四块，三块的情况是两线没有交叉，四块的情况是两线交叉了，我们考虑从时钟的最外面走一圈，若出现交叉的情况输出 \(4\) 否则输出 \(3\) 即可。
#include <bits/stdc++.h>
#define int long longusing namespace std;void solve(){int a,b,c,d; cin>>a>>b>>c>>d;string s;for(int i = 1;i<=12;i++){if(i == a || i == b) s += "0";if(i == c || i == d) s += "1";}if(s[0] == s[2] && s[1] == s[3]) cout<<4<<endl;else cout<<3<<endl;
}signed main(){freopen("time.in","r",stdin);freopen("time.out","w",stdout);int T; cin>>T; while(T--)solve();return 0;
}
B题
背包DP缝合题（？）带双重容量+种类01背包，挺板的
DP状态转移方程：
\[dp[pi][li]=max(dp[pi][li],dp[pi-p[i]][li-l[i]]+b[i])
\]
#include <bits/stdc++.h>
#define int long long
using namespace std;const int N=1e3+5;int n,t,w,k[N];
int p[N],l[N],b[N];
int dp[N][N];void solve(){cin>>n>>t>>w;for(int i=1;i<=n;i++) cin>>k[i];for(int i=1;i<=n;i++) cin>>p[i]>>l[i]>>b[i];for(int i=1;i<=n;i++){while(k[i]--){for(int pi=w;pi>=p[i];pi--){for(int li=t;li>=l[i];li--){dp[pi][li]=max(dp[pi][li],dp[pi-p[i]][li-l[i]]+b[i]);}}}}cout<<dp[w][t]<<endl;
}signed main(){freopen("hui.in","r",stdin);freopen("hui.out","w",stdout);// int T; cin>>T; while(T--)solve();
}
C题
模拟题，直接模拟即可，注意一下pow会爆，要自己写 \(10^n\) ，右边补一就 n*=10,n++ 即可，左边补 3 就直接加 \(3\times 10^{len+i-1}\)。
#include <bits/stdc++.h>
#define int long longusing namespace std;const int mod = 1e9 + 7;int x;void solve(){cin>>x;int cs = x;for(int k = 1;k<=cs;k++){int cnt0 = 0,cnt1 = 0,cnt2 = 0,cnt3 = 0;int tmp = x;while(tmp){if(tmp % 10 == 0) cnt0++;else if(tmp % 10 == 1) cnt1++;else if(tmp % 10 == 2) cnt2++;else if(tmp % 10 == 3) cnt3++;tmp/=10;}for(int i = 1;i<=cnt0;i++) x*=10,x++;for(int i = 1;i<=cnt1;i++) x*=2;tmp = x;int len = 0;while(tmp)len++,tmp/=10;for(int i = 1;i<=cnt2;i++){int add = 3;for(int j = 1;j<=len+i-1;j++) add *= 10;x += add;}if(cnt3) x += 123456;x += k;x %= mod;// cout<<x<<endl;}cout<<x<<endl;
}signed main(){freopen("all.in","r",stdin);freopen("all.out","w",stdout);// int T; cin>>T; while(T--)solve();return 0;
}
D题
双指针题，考虑每一种类的每个人都扔到一个数组里，然后双指针维护即可，种类数 \(< n\) 右边界右移，否则左边界右移，种类数达到 \(n\) 更新答案最小值，极差使用 set 进行维护（要重载运算符）
下面的代码只有 \(70\) 分，不知道挂哪了，待调。
#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 1e6 + 3;int n;
int vis[N];struct node{int c,t;bool operator <(const node &x)const{return t < x.t;}
};
vector<node> a;
set<node> s;bool cmp(node x,node y){return x.t < y.t;
}void solve(){cin>>n;for(int i = 1;i<=n;i++){int ci; cin>>ci;for(int j = 1;j<=ci;j++){int t; cin>>t;a.push_back((node){i,t});}}sort(a.begin(),a.end(),cmp);int l = 0,r = 0;int ans = LONG_LONG_MAX;int kind = 0;while(l <= r && r<a.size()){if(kind<n){r++;s.insert(a[r-1]);vis[a[r-1].c]++;if(vis[a[r-1].c] == 1) kind++;} else {auto it = s.end(); it--;node ma = *it;node mi = *s.begin();ans = min(ans,ma.t - mi.t);s.erase(a[l]);vis[a[l].c]--;if(!vis[a[l].c]) kind--;l++;}}cout<<ans<<endl;
}signed main(){freopen("buhezuo.in","r",stdin);freopen("buhezuo.out","w",stdout);// int T; cin>>T; while(T--)solve();return 0;
}
