[考试反思]1113csp-s模拟测试113：一念

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

在这么考下去可以去混女队了2333

两天总分rank14，退役稳稳的

的确就是没状态。满脑子都是《包围保卫王国》ddp/LCT/ST，没好好考试。

我太菜了写题也写不出来考试也考不好（显然《保卫王国》40分钟是调不出来的）

也不知道为什么特别想A了它。。。莫名的执念

也许所谓的OI也就是一念之间的问题吧。

T1：ZYB修围墙

答案有可能是偶数。扩展一面墙的时候相对的墙不一定要扩展。

边长为a时，6次扩展的收益分别为a,a-1,a,a,a,a

 #include<cstdio>

 main(){

     freopen("wall.in","r",stdin);freopen("wall.out","w",stdout);

     int n,cnt=,i=;scanf("%d",&n);

     for(;cnt<n;++i,cnt+=i/-(i%==));

     printf("%d\n",i);

 }

T2：ZYB和售货机

每个物品多数情况下只会被以最低的买入价格买入。这样形成建边关系。

然后如果图里没有环那么收益就是最低价买入后卖出。（40pts）

否则，对于环上的所有点，其中有一个必须以次低价买入。

统计一下这样的亏损，取环上最小的亏损值从答案里减去即可。

 #include<cstdio>

 #include<iostream>

 using namespace std;

 #define S 100005

 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;

 int sta[S],top,sec[S];

 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;}

 void dfs(int p){

     al[p]=;sta[++top]=p;

     for(int i=fir[p];i;i=l[i])if(!al[to[i]])dfs(to[i]);

         else if(to[i]==p)continue;

         else if(al[to[i]]==){

             int mn=<<,j=;sta[top+]=to[i];

             while(sta[j]!=to[i])j++;

             for(;j<=top;++j)

                 mn=min(mn,d[sta[j+]]-c[sta[j]]-max(,-sec[sta[j+]]+d[sta[j+]]));

             ans-=mn;

         }

     al[p]=;top--;

 }

 int main(){

     freopen("goods.in","r",stdin);freopen("goods.out","w",stdout);

     scanf("%d",&n);

     for(int i=;i<=n;++i)scanf("%d%d%d%d",&f[i],&c[i],&d[i],&a[i]),mn[i]=sec[i]=;

     for(int i=;i<=n;++i)if(mn[f[i]]>c[i])mn[f[i]]=c[i],ord[f[i]]=i;

     for(int i=;i<=n;++i)if(mn[i]<d[i])ans+=1ll*a[i]*(d[i]-mn[i]),link(ord[i],i);

     for(int i=;i<=n;++i)if(sec[f[i]]>c[i]&&i!=ord[f[i]])sec[f[i]]=c[i];

     for(int i=;i<=n;++i)if(!al[i])top=,dfs(i);

     printf("%lld\n",ans);

 }

样例的环是假的（不是最大收益环，有负收益）

所以提供一组AKT的极其简单的调试用hack数据：（干掉了我的考场40分代码）

input:

output:

T3：ZYB玩字符串

cbx没脸粘我代码。 (不知道为什么他不让我只重复两遍)

cbx没脸粘我代码。

看懂题目并且打一个搜索就可以获得90分。（有哪个剪枝不明白是干什么用的的话可以去问我）

 #include<bits/stdc++.h>

 using namespace std;

 map<string,int>M;

 int lim,n,len,cnt[],tcnt[],used[],fin;string s,chk,ans;

 int gcd(int a,int b){return b?gcd(b,a%b):a;}

 bool sch(int l,int num){

     if(num+fin>lim)return false;

     if(l==n)return true;

     if(chk[]==s[l]){

         used[num+]=;

         if(sch(l+,num+))return true;

         used[num+]=;

     }

     if(chk[used[num]]==s[l]){

         used[num]++;int nt=;

         if(used[num]==len)num--,fin++,nt=;

         if(sch(l+,num))return true;

         if(nt)num++,fin--;

         used[num]--;

     }

     return false;

 }

 int main(){

     freopen("string.in","r",stdin);freopen("string.out","w",stdout);

     int t;scanf("%d",&t);

     while(t--){

         cin>>s;n=s.length();reverse(s.begin(),s.end());ans="";M.clear();

         for(int i=;i<;++i)cnt[i]=;

         for(int i=;i<n;++i)cnt[s[i]-'a']++;

         int g=;

         for(int pt=;pt<;++pt)g=gcd(g,cnt[pt]);

         for(len=;len<=n;++len)if(n%len==){

             lim=n/len;if(lim>g)continue;

             for(int st=;st+len-<n;++st)if(s[st]==s[]&&s[n-]==s[st+len-]){

                 chk="";

                 for(int i=;i<;++i)tcnt[i]=;

                 for(int i=st;i<=st+len-;++i)chk+=s[i],tcnt[s[i]-'a']++;

                 if(M[chk])goto ed;M[chk]=;

                 for(int i=;i<;++i)if(cnt[i]&&(!tcnt[i]||cnt[i]%tcnt[i]||cnt[i]/tcnt[i]!=lim))goto ed;

                 for(int i=;i<=lim+;++i)used[i]=;fin=;

                 if(sch(,)){reverse(chk.begin(),chk.end());if(ans.empty())ans=chk;else ans=min(ans,chk);}ed:;

             }

             if(!ans.empty())break;

         }cout<<ans<<endl;

     }

 }

除了测试点9一共190ms

考场上想到应该是个dp但是想不到定义。dp[i][j]表示[i,j]段除了前(j-i)%len位完美匹配了整串前缀以外剩下的位置也可以被完美消除。

考虑每一位加入的贡献。（我的字符串下标从0开始，s表示原串，chk表示当前）

dp[i][j]|=dp[i][j-1]&(s[j]==chk[(j-i)%len])。就是在最后多匹配了一位。

dp[i][j]|=dp[i][j-k*len]&dp[j-k*len+1][j]。就是后面有几个完整的段被吃掉了。

从含义上理解，这已经包含了所有情况。

初始状态就是所有空串都是合法的，其余都是0。

加上考场上的剪枝，效率极其优秀。

到底有多优秀，去看cbx卡成了什么样子吧。。。

cbx没脸粘我代码。

 #include<bits/stdc++.h>

 using namespace std;

 map<string,int>M;

 int lim,n,len,cnt[],tcnt[];string s,chk,ans;

 int gcd(int a,int b){return b?gcd(b,a%b):a;}

 bool dp[][];

 bool sch(){

     for(int i=;i<n;++i)for(int j=i;j<n;++j)dp[i][j]=;

     for(int i=;i<n;++i)dp[i][i-]=;

     dp[][]=;

     for(int i=;i<n;++i){

         if(i)for(int j=;j<=i;++j)dp[j][i]|=dp[j][i-]&(s[i]==chk[(i-j)%len]);

         if(s[i]==chk[len-])for(int j=;j<=i;++j)for(int k=;j<=i-k*len+;++k)

             dp[j][i]|=dp[j][i-k*len]&dp[i-k*len+][i];

     }

     return dp[][n-];

 }

 int main(){

     freopen("string.in","r",stdin);freopen("string.out","w",stdout);

     int t;scanf("%d",&t);

     while(t--){

         cin>>s;n=s.length();ans="";M.clear();

         for(int i=;i<;++i)cnt[i]=;

         for(int i=;i<n;++i)cnt[s[i]-'a']++;

         int g=;

         for(int pt=;pt<;++pt)g=gcd(g,cnt[pt]);

         for(len=;len<=n;++len)if(n%len==){

             lim=n/len;if(lim>g)continue;

             for(int st=;st+len-<n;++st)if(s[st]==s[]&&s[n-]==s[st+len-]){

                 chk="";

                 for(int i=;i<;++i)tcnt[i]=;

                 for(int i=st;i<=st+len-;++i)chk+=s[i],tcnt[s[i]-'a']++;

                 if(!ans.empty()&&chk>ans)goto ed;

                 if(M[chk])goto ed;M[chk]=;

                 for(int i=;i<;++i)if(cnt[i]&&(!tcnt[i]||cnt[i]%tcnt[i]||cnt[i]/tcnt[i]!=lim))goto ed;

                 if(sch())if(ans.empty())ans=chk;else ans=min(ans,chk);ed:;

             }

             if(!ans.empty())break;

         }cout<<ans<<endl;

     }

 }