T1:传纸条

Problem:

小 S 和小 V 上课喜欢传纸条。 传纸条是有风险的，为了在老师发现的时候不知道他们在讨论什么内容，他们发明了一系列的加密方式。 其中有一种是这样的：一个数字由两个字符串 a 和 b 表达，这个数字就是 b 在 a 中匹配的位置。比如，a=”abcd”，b=”c”，那么这个数字就是 3。 但是这样会出现一个问题，a 和 b 能够表达两个不同的数字：比如，a=“ababa”，b=”aba”时，那个数字可以是 1 也可以是 3。他们对这种现象很好奇 现在给定一个字符串 a，求一个整数 x 使得对于任意一个长度大于 x 的串 b，这一问题都不会出现。

Code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=110000;
 4 int tr[maxn][26],len,flag;
 5 int tar[maxn],cnt;
 6 void Insert(string s){
 7      int now=0;
 8      for(int i=1;s[i];i++){
 9          if(!tr[now][s[i]-'a']) tr[now][s[i]-'a']=++cnt;
10          now=tr[now][s[i]-'a'];
11      }
12      tar[now]++;
13      if(tar[now]>=2) flag=1;
14 }
15 string s;
16 bool check(int now){
17      memset(tr,0,sizeof(tr));
18      memset(tar,0,sizeof(tar));
19      flag=0;
20      cnt=0;
21      for(int l=1;l+now-1<=len;l++){
22           string mid=" ";
23           for(int i=l;i<=l+now-1;i++) mid+=s[i];
24           Insert(mid);
25           if(flag==1) return true;
26      }
27      return false;
28 }
29 int main(){
30     cin>>s;
31     len=s.length();
32     int l=0,r=len;
33     s=' '+s;
34     int mid,ans;
35     while(l<=r){
36         int mid=(l+r)>>1;
37         if(check(mid)){
38             ans=mid;
39             l=mid+1;
40         }
41         else r=mid-1;
42     }
43     cout<<ans;
44     return 0;
45 }

T2:合并序列

Problem:

给定 K 个数字序列，请将它们合并为一个，满足本来在同一序列中的两个数的相对位置不变。 定义一个序列 A 的不和谐度为序列中使得A[i] > A[i + 1]成立的 i 的总数，请输出一种合并方案，使得合并后的序列不和谐度最小。

Code:

 1 #include<bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int num,pre,nw,ans;
 5 signed main(){
 6     scanf("%lld",&num);
 7     for(int i=1;i<=num;++i){
 8         int len,fir,x,y,p;
 9         scanf("%lld%lld%lld%lld%lld",&len,&fir,&x,&y,&p);
10         int pre=fir,nw,tot=0;
11         for(int j=2;j<=len;++j){
12             nw=(pre*x+y)%p;
13             if(pre>nw) tot++;
14             pre=nw;
15         }
16         ans=max(ans,tot);
17     }
18     cout<<ans<<endl;
19     return 0;
20 }

T3:密码锁

Problem:

一个密码锁上有 N 个指示灯，从左到右编为 1～N 号。每个指示灯有开关两种状态。初始时有 K 个指示灯 x[1], x[2] .. x[k]处于开状态，其它的灯均处在关状态。当所有灯均被关闭时，密码锁会自动打开。 密码锁上有 L 个按钮。每个按钮 i 有一个参数 L[i]。每次操作时，你可以按下某个按钮i，选择连续的 L[i]个指示灯，并将它们的状态取反（开->关，关->开）。 请编程计算解锁的最少操作次数。

Code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=4e4+1;
 4 const int Cnt=2e2+1;
 5 const int M=(1<<20);
 6 int n,k,m;
 7 bool Vis[maxn],C[maxn],op[M];
 8 int num[maxn],tot,b[maxn],dp[M];
 9 int D[Cnt][maxn],w[maxn];
10 class Node{
11 public:
12     int to,dis;
13     Node(int a,int b):dis(a),to(b){}
14 };
15 queue<Node>Q;
16 inline void Find(int id,int nid){
17     memset(w,0x3f,sizeof(w));
18     Q.push(Node(0,id));
19     while(!Q.empty()){
20         Node now=Q.front();
21         Q.pop();
22         int l=now.to,a=now.dis;
23         if(w[l]<=a) continue;
24         w[l]=a;
25         for(int i=1;i<=m;++i){
26             if(l+b[i]<=n+1) Q.push(Node(a+1,l+b[i]));
27             if(l-b[i]>=1) Q.push(Node(a+1,l-b[i]));
28         }
29     }
30     for(int i=1;i<=tot;++i) D[nid][i]=w[num[i]];
31 }
32 inline int Dfs(int x){
33     if(op[x]) return dp[x];
34     for(int i=1;i<=tot;++i){
35         if(x&(1<<(i-1))){
36             for(int j=i+1;j<=tot;++j){
37                 if(x&(1<<(j-1))){
38                     int np=(1<<(j-1)),nx=(1<<(i-1));
39                     int nw=Dfs(x^np^nx);
40                     dp[x]=min(dp[x],nw+D[i][j]);
41                 }
42             }
43         }
44     }
45     op[x]=true;
46     return dp[x];
47 }
48 signed main(){
49     scanf("%d%d%d",&n,&k,&m);
50     memset(dp,0x3f,sizeof(dp));
51     for(int i=0;i<=n+1;++i) Vis[i]=1;
52     for(int i=1;i<=k;++i){
53         int t;
54         scanf("%d",&t);
55         Vis[t]=0;
56     }
57     for(int i=1;i<=m;++i) scanf("%d",&b[i]);
58     for(int i=1;i<=n+1;++i){
59         (C[i]=Vis[i-1]^Vis[i])and(num[++tot]=i);
60     }
61     for(int i=1;i<=tot;++i) Find(num[i],i);
62     dp[0]=0;
63     int ans=Dfs((1<<tot)-1);
64     if(ans==0x3f3f3f3f) ans=-1;
65     printf("%d\n",ans);
66     return 0;
67 }