[考试反思]1113csp-s模拟测试113：一念
在这么考下去可以去混女队了2333
两天总分rank14，退役稳稳的
的确就是没状态。满脑子都是《包围保卫王国》ddp/LCT/ST，没好好考试。
我太菜了写题也写不出来考试也考不好（显然《保卫王国》40分钟是调不出来的）
也不知道为什么特别想A了它。。。莫名的执念
也许所谓的OI也就是一念之间的问题吧。
T1：ZYB修围墙
答案有可能是偶数。扩展一面墙的时候相对的墙不一定要扩展。
边长为a时，6次扩展的收益分别为a,a-1,a,a,a,a
1 #include<cstdio> 2 main(){ 3 freopen("wall.in","r",stdin);freopen("wall.out","w",stdout); 4 int n,cnt=1,i=6;scanf("%d",&n); 5 for(;cnt<n;++i,cnt+=i/6-(i%6==1)); 6 printf("%d ",i); 7 }
T2：ZYB和售货机
每个物品多数情况下只会被以最低的买入价格买入。这样形成建边关系。
然后如果图里没有环那么收益就是最低价买入后卖出。（40pts）
否则，对于环上的所有点，其中有一个必须以次低价买入。
统计一下这样的亏损，取环上最小的亏损值从答案里减去即可。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define S 100005 5 int f[S],c[S],d[S],a[S],n,mn[S],ord[S],al[S],fir[S],l[S],to[S],ec;long long ans; 6 int sta[S],top,sec[S]; 7 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;} 8 void dfs(int p){ 9 al[p]=2;sta[++top]=p; 10 for(int i=fir[p];i;i=l[i])if(!al[to[i]])dfs(to[i]); 11 else if(to[i]==p)continue; 12 else if(al[to[i]]==2){ 13 int mn=1<<30,j=0;sta[top+1]=to[i]; 14 while(sta[j]!=to[i])j++; 15 for(;j<=top;++j) 16 mn=min(mn,d[sta[j+1]]-c[sta[j]]-max(0,-sec[sta[j+1]]+d[sta[j+1]])); 17 ans-=mn; 18 } 19 al[p]=1;top--; 20 } 21 int main(){ 22 freopen("goods.in","r",stdin);freopen("goods.out","w",stdout); 23 scanf("%d",&n); 24 for(int i=1;i<=n;++i)scanf("%d%d%d%d",&f[i],&c[i],&d[i],&a[i]),mn[i]=sec[i]=1000005; 25 for(int i=1;i<=n;++i)if(mn[f[i]]>c[i])mn[f[i]]=c[i],ord[f[i]]=i; 26 for(int i=1;i<=n;++i)if(mn[i]<d[i])ans+=1ll*a[i]*(d[i]-mn[i]),link(ord[i],i); 27 for(int i=1;i<=n;++i)if(sec[f[i]]>c[i]&&i!=ord[f[i]])sec[f[i]]=c[i]; 28 for(int i=1;i<=n;++i)if(!al[i])top=0,dfs(i); 29 printf("%lld ",ans); 30 }
样例的环是假的（不是最大收益环，有负收益）
所以提供一组AKT的极其简单的调试用hack数据：（干掉了我的考场40分代码）
input:
6 2 1 11 2 3 1 12 2 1 1 13 2 1 5 0 2 2 4 0 2 3 3 0 2
output:
64
T3：ZYB玩字符串
cbx没脸粘我代码。(不知道为什么他不让我只重复两遍)
cbx没脸粘我代码。
看懂题目并且打一个搜索就可以获得90分。（有哪个剪枝不明白是干什么用的的话可以去问我）
1 #include<bits/stdc++.h> 2 using namespace std; 3 map<string,int>M; 4 int lim,n,len,cnt[26],tcnt[26],used[222],fin;string s,chk,ans; 5 int gcd(int a,int b){return b?gcd(b,a%b):a;} 6 bool sch(int l,int num){ 7 if(num+fin>lim)return false; 8 if(l==n)return true; 9 if(chk[0]==s[l]){ 10 used[num+1]=1; 11 if(sch(l+1,num+1))return true; 12 used[num+1]=0; 13 } 14 if(chk[used[num]]==s[l]){ 15 used[num]++;int nt=0; 16 if(used[num]==len)num--,fin++,nt=1; 17 if(sch(l+1,num))return true; 18 if(nt)num++,fin--; 19 used[num]--; 20 } 21 return false; 22 } 23 int main(){ 24 freopen("string.in","r",stdin);freopen("string.out","w",stdout); 25 int t;scanf("%d",&t); 26 while(t--){ 27 cin>>s;n=s.length();reverse(s.begin(),s.end());ans="";M.clear(); 28 for(int i=0;i<26;++i)cnt[i]=0; 29 for(int i=0;i<n;++i)cnt[s[i]-'a']++; 30 int g=0; 31 for(int pt=0;pt<26;++pt)g=gcd(g,cnt[pt]); 32 for(len=1;len<=n;++len)if(n%len==0){ 33 lim=n/len;if(lim>g)continue; 34 for(int st=0;st+len-1<n;++st)if(s[st]==s[0]&&s[n-1]==s[st+len-1]){ 35 chk=""; 36 for(int i=0;i<2;++i)tcnt[i]=0; 37 for(int i=st;i<=st+len-1;++i)chk+=s[i],tcnt[s[i]-'a']++; 38 if(M[chk])goto ed;M[chk]=1; 39 for(int i=0;i<2;++i)if(cnt[i]&&(!tcnt[i]||cnt[i]%tcnt[i]||cnt[i]/tcnt[i]!=lim))goto ed; 40 for(int i=1;i<=lim+1;++i)used[i]=0;fin=0; 41 if(sch(0,1)){reverse(chk.begin(),chk.end());if(ans.empty())ans=chk;else ans=min(ans,chk);}ed:; 42 } 43 if(!ans.empty())break; 44 }cout<<ans<<endl; 45 } 46 }