这场打的跟狗屎一样的惨
签到题
/*简化版*/ #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=(b);++i) #define mem(a,x) memset(a,x,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; const int N=1e5+10; string s,t; int a[30]; int getid(char x) { if(x=='h') return 1; if(x=='d') return 2; return 3; } int main() { int _; cin>>_; int cas=0; while(_--) { cin>>s>>t; for(int i=0;i<26;++i) { a[i]=getid(t[i]); } int num[4]; num[1]=num[2]=num[3]=0; for(int i=0;i<s.size();++i) { num[a[s[i]-'a']]++; } //printf("s.z:%d\n",s.size()); //for(int i=1;i<=3;++i) printf("i:%d num[i]:%d\n",i,num[i]); int n=s.size(); if(100*num[1]>=25*n){ printf("Case #%d: Harmful\n",++cas); } else if(100*num[1]<=10*n) printf("Case #%d: Recyclable\n",++cas); else if(num[2]>=2*num[3]) printf("Case #%d: Dry\n",++cas); else printf("Case #%d: Wet\n",++cas); } }128位的二进制，化成16进制，每四位合在一起，四位与四位用"："分割，对单独四位而言m前导0可省略，四个0省略成一个0，
问现能将两个0合并成"::"问字典序最小的一个字符是什么？
暴力枚举0的位置变成"::"求字典序最小的即可
#include<bits/stdc++.h> using namespace std; string s,ans; char tmx[20]="0123456789abcdef"; char cal1(int id) { int tmp=0; int ans=0; for(int i=id;i>=id-3;--i) { if(s[i]=='1') ans+=pow(2,tmp); ++tmp; } return tmx[ans]; } struct node { int x; string val; }a[10000]; int main() { int cas=0; int _; cin>>_; while(_--) { cin>>s; int l1=s.size(); string t; for(int i=3;i<l1;i+=4) { t+=cal1(i); } //cout<<"t:"<<t<<endl; string t1; int cnt=0; ans=""; for(int i=0;i<t.size();i+=4) { int j=i; ++cnt; while(j<=i+3&&t[j]=='0')++j; while(j<=i+3) a[cnt].val+=t[j],++j; if(t[i]=='0'&&t[i+1]=='0'&&t[i+2]=='0'&&t[i+3]=='0') a[cnt].x=1; } //printf("cnt:%d\n",cnt); for(int i=1;i<=cnt;++i) { if(a[i].x==1) ans+="0"; else ans+=a[i].val; if(i!=cnt)ans+=":"; } for(int i=1;i<=cnt;++i) { if(a[i].x==1) { int j=i; int num=0; while(j<=cnt&&a[j].x==1) ++j,num++; if(num<2) continue; string tmp=""; //printf("i:%d j:%d\n",i,j); for(int k=1;k<i;++k) { if(a[k].x==1) tmp+="0"; else tmp+=a[k].val; tmp+=":"; } if(i==1) tmp+=":"; tmp+=":"; for(int k=j;k<=cnt;++k) { if(a[k].x==1) tmp+="0"; else tmp+=a[k].val; tmp+=":"; } //cout<<"tmp: "<<tmp<<endl; if(tmp[tmp.size()-1]==':'&&tmp[tmp.size()-2]!=':') tmp.erase(tmp.size()-1); if(ans=="") ans=tmp; else { if(tmp.size()<ans.size()) ans=tmp; else if(tmp.size()==ans.size()&&tmp<ans) ans=tmp; } i=j; } } printf("Case #%d: ",++cas);cout<<ans<<endl; for(int i=0;i<=cnt;++i) a[i].val="",a[i].x=0; } }题意：给定n个物品，k个体积相等的盒子，求一个最小体积使得所有的物品都可以装到盒子里。装盒子要满足有大的就装大的，没有大的才能装小的的策略
不可二分
暴力枚举体积，然后从大到小二分插入容量即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+10; ll v[N]; int main() { int _;cin>>_; int cas=0; while(_--) { int n,k; scanf("%d%d",&n,&k); multiset<ll>st; ll sum=0; ll mx=0; for(int i=1;i<=n;++i) { scanf("%lld",&v[i]); mx=max(mx,v[i]); sum+=v[i]; } ll flag=0; if(sum%k!=0) flag=1; ll v1=max(mx,sum/k+flag); for(ll i=v1;;++i) { ll ans=i; int k0=1; st.clear(); for(int j=1;j<=n;++j) st.insert(v[j]); while(k0<=k) { ll v2=ans; while(v2>0&&st.size()) { auto it=st.upper_bound(v2); if(it==st.begin()) break; --it; v2-=*it; st.erase(it); } ++k0; } if(st.size()==0) { printf("Case #%d: %lld\n",++cas,ans); break; } } } }蔡勒公式。
1582年10月4日后：w = (d + 1+ 2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;（包括当年）
1582年10月4日前：w = (d+1+2*m+3*(m+1)/5+y+y/4+5) % 7;
w：星期； w对7取模得：0-星期日，1-星期一，2-星期二，3-星期三，4-星期四，5-星期五，6-星期六
c：世纪（注：一般情况下，在公式中取值为已经过的世纪数，也就是年份除以一百的结果，而非正在进行的世纪，也就是现在常用的年份除以一百加一；不过如果年份是公元前的年份且非整百数的话，c应该等于所在世纪的编号，如公元前253年，是公元前3世纪，c就等于-3）
y：年（一般情况下是后两位数，如果是公元前的年份且非整百数，y应该等于cMOD100+100）
m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）
d：日
[ ]代表取整，即只要整数部分。
此题做法：dfs暴力枚举每个数字用相应的字符对应的序列，然后依次判断所有字符是否合法（是星期五）
【代码】
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; string s[N]; int n; bool flag; int val[30]; int vis[30]; bool isyear(int x) { if(x%4==0&&x%100!=0||x%400==0) return 1; return 0; } int Zeller(int y,int m,int d) { if (m == 1 || m == 2) { y -= 1; m += 12; } /*只适用于1582年之后，不包括当年*/ /*1582年之后之前：w = (d + 1+ 2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7*/ return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1)%7; } bool check() { for(int i=0;i<n;++i) { int year=0,month=0,day=0; for(int j=0;j<=3;++j) year=year*10+val[s[i][j]-'A']; for(int j=5;j<=6;++j) month=month*10+val[s[i][j]-'A']; for(int j=8;j<=9;++j) day=day*10+val[s[i][j]-'A']; if(year<1600||month>12||month<1||day>31||day<1) return 0; if((month==4||month==6||month==9||month==11)&&day>30) return 0; if(isyear(year)&&month==2&&day>29) return 0; if(!isyear(year)&&month==2&&day>28) return 0; if(Zeller(year,month,day)!=5) return 0; } return 1; } void dfs(int now) { if(flag) return ; if(now==10) { if(check()) { flag=1; for(int i=0;i<10;++i) { printf("%d",val[i]); } puts(""); } return ; } for(int i=0;i<10;++i) { if(vis[i]==0) { vis[i]=1; val[now]=i; dfs(now+1); vis[i]=0; } } } int main() { int _; cin>>_; int cas=0; while(_--) { memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i=0;i<n;++i) cin>>s[i]; sort(s,s+n); n=unique(s,s+n)-s; flag=0; printf("Case #%d: ",++cas); dfs(0); if(!flag) printf("Impossible\n"); } return 0; }签到题
/*简化版*/ #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=(b);++i) #define mem(a,x) memset(a,x,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; const int N=1e3+50; const ll inf=0x3f3f3f3f3f3f3f; int n,m; ll d[N],a[N][N],b[N]; ll last[N][N],pre[N]; ll mx[N][N*4]; vector<ll>G; void up(int id,int l,int r,int ty) { if(l==r) { mx[ty][id]=last[ty][l]; return ; } int mid=l+r>>1; up(id<<1,l,mid,ty); up(id<<1|1,mid+1,r,ty); mx[ty][id]=max(mx[ty][id<<1],mx[ty][id<<1|1]); } ll qu(int id,int l,int r,int ty,int ql,int qr) { if(ql<=l&&r<=qr) return mx[ty][id]; int mid=l+r>>1; ll ans=-inf; if(ql<=mid) ans=max(ans,qu(id<<1,l,mid,ty,ql,qr)); if(qr>mid) ans=max(ans,qu(id<<1|1,mid+1,r,ty,ql,qr)); return ans; } bool cmp(int x,int y) { return x>y; } int main() { int _; cin>>_; int cas=0; while(_--) { scanf("%d %d",&n,&m); for(int i=0;i<=1010;++i) { b[i]=pre[i]=d[i]=0; for(int j=0;j<=1010;++j) last[i][j]=0; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { scanf("%lld",&a[i][j]); a[i][j]=-a[i][j]; } for(int i=1;i<=m;++i){ scanf("%lld",&d[i]); pre[i]=pre[i-1]+d[i]; } for(int j=1;j<=m;++j) { ll tmp=0; for(int i=1;i<=n;++i) { tmp+=a[i][j]; } b[j]=b[j-1]+tmp; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) last[i][j]=last[i][j-1]+a[i][j]; for(int i=1;i<=n;++i) up(1,1,m,i); ll ans=0; for(int j=0;j<=m;++j) { ll tmp=pre[j]+b[j]; G.clear(); for(int i=1;i<=n;++i) { if(j+1<=m) { ll qut=qu(1,1,m,i,j+1,m); if(qut-last[i][j]>0) G.push_back(qut-last[i][j]); else G.push_back(0); } else G.push_back(0); } sort(G.begin(),G.end(),cmp); for(int i=0;i<n-1;++i){ if(G[i]>0) tmp+=G[i]; } ans=max(ans,tmp); } printf("Case #%d: %lld\n",++cas,ans); } return 0; }
