B. Split a Number
给定一个n位的数字 将其分为两个数字 （直接截断） 要求最小化其和 并输出 两个数字都不包含前导0
这题弄了半天 主要是考虑前导零的问题 （主要贪心原则是从中间分为两段 如果是奇数的话要考虑两种分法）
可以直接定位到前一段 n/2 就是 如果有0的话 while-- 然后再pos++ 如果有0的话 while++
这样就提取除两段数字了 再用高精度搞一下就好啦
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 ////////////////////////////////// const int N=1e6+5; int n,cnt; string s1,s2,s; string ok(string a,string b) { if(b.size()>a.size() )swap(a,b); int lena=a.size(),lenb=b.size(); a='0'+a; int L=b.size()-1; for(int i=lena;i>=1;--i ) { a[i]+=b[L]-'0'; if(a[i]>'9')a[i]-=10,a[i-1]++; L--; if(L==-1) { L=0;b[L]='0'; } } if(a[0]=='0')return a.substr(1,a.size()-1); return a; } int main() { cin>>n; cin>>s; int temp1=n/2; while(s[temp1]=='0')temp1--; string ans=ok( s.substr(0,temp1),s.substr(temp1,n-(temp1-1) )); temp1++; while(s[temp1]=='0')temp1++; string ans2=ok( s.substr(0,temp1),s.substr(temp1,n-(temp1-1) )); if(ans.size()<ans2.size()) cout<<ans; else if(ans.size()>ans2.size()) cout<<ans2; else if(ans.size()==ans2.size()) { if(ans<ans2)cout<<ans; else cout<<ans2; } return 0; }
C. Flag
求布条个数 布条必须满足：
由三个相同高度的条纹组成 相邻条纹颜色不同 参考国旗
非常好的一道dp题 可以右下角为点进行dp
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=1000+5; int n,m,f[N][N],g[N][N],la,ans,v; char mp[N][N]; int judge(int i,int j) { int len=g[i][j]; i-=len; if(g[i][j]!=len)return 0; i-=len; return len*(g[i][j]>=len); } int main() { RII(n,m); rep(i,1,n)RS(mp[i]+1); rep(i,1,n)rep(j,1,m) if(mp[i][j]==mp[i-1][j]&&i!=1)g[i][j]=g[i-1][j]+1; else g[i][j]=1; rep(i,1,n)rep(j,1,m) { v=judge(i,j); if(!v){la=0;continue;} f[i][j]=1; if(la==v&&mp[i][j-1]==mp[i][j]&&mp[i-v][j-1]==mp[i-v][j]&&mp[i-2*v][j-1]==mp[i-2*v][j] ) f[i][j]+=f[i][j-1]; ans+=f[i][j]; la=v; } cout<<ans; return 0; }
D. Irrigation
m个城市 举行IOI竞赛 优先级是 举办此时小于其他城市的先举办 如果举办次数相同 城市编号小的先举办
给出n个数字 表示第i年时 ai 城市举办
然后给出q个询问 （q>n+1) 问第qi年是第几个城市举办
显然 到一定程度的时候是循环
一开始用优先队列来模拟 结果直接爆掉了
题解：
https://edwiv.com/archives/613
非常好的题目！！！！
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=2e6+10; int n,m,q,x; ll cnt[N],a[N]; int main() { RIII(n,m,q); rep(i,1,n)RI(x),a[i]=(cnt[x]++)*m+x; sort(a+1,a+1+n); rep(i,1,n)a[i]-=i; rep(i,1,q) { ll t;scanf("%lld",&t);t-=n; if(t>a[n])t+=n; else t+=lower_bound(a+1,a+1+n,t)-a-1; t%=m;if(!t)t=m; printf("%d ",t); } }