Codeforces Round #305 (Div. 2)

A:检查是否回文。模拟一边。

 1  
 2 #include<stdio.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 #include<string.h>
 6 #include<iostream>
 7 #include<set>
 8 #include<time.h>
 9 #include<vector>
10 
11 using  namespace std;
12 typedef long long ll;
13 #define N 1234567
14 #define inf 0x3f3f3f3f
15  string s;
16 
17  int pan(int x,int y)
18  {
19       y--;
20       while (x<y)
21       {
22       if (s[x]!=s[y]) return 0;
23       x++;y--;
24       }
25      return 1;
26  }
27 
28 int main()
29 {
30 
31   int k;
32   cin>>s>>k;
33   int n=s.size();
34   if (n%k)
35   {
36       cout<<"NO";
37       return 0;
38   }
39   int tmp=n/k;
40   for (int i=0;i<n;i+=tmp)
41   {
42       int j=i+tmp;
43       if (!pan(i,j))
44       {
45         //  cout<<i<<" "<<j<<endl;
46           cout<<"NO";
47           return 0;
48       }
49   }
50     cout<<"YES";
51     return 0;
52 }

View Code

B:用m*n*m 模拟一边；

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<algorithm>
 4 #include<string.h>
 5 #include<iostream>
 6 #include<set>
 7 #include<time.h>
 8 #include<vector>
 9 
10 using  namespace std;
11 typedef long long ll;
12 #define N 1234567
13 #define inf 0x3f3f3f3f
14 
15 int mp[555][555];
16 int a[555];
17 
18 int main()
19 {
20 
21     int n,m,q;
22     cin>>n>>m>>q;
23 
24     for (int i=1;i<=n;i++)
25     for (int j=1;j<=m;j++)
26     {
27         cin>>mp[i][j];
28     }
29 
30     for (int i=1;i<=n;i++)
31     {
32         int tmp=0;
33         for (int j=1;j<=m;j++){
34         if (mp[i][j]) tmp++;
35         else tmp=0;
36         a[i]=max(a[i],tmp);
37         }
38     }
39 
40     while (q--)
41     {
42         int x,y;
43         cin>>x>>y;
44         if (mp[x][y])
45         {
46             mp[x][y]=0;
47         }
48         else
49         {
50             mp[x][y]=1;
51         }
52         a[x]=0;
53             int tmp=0;
54             for (int j=1;j<=m;j++){
55             if (mp[x][j]) tmp++;
56             else tmp=0;
57             a[x]=max(a[x],tmp);
58             }
59 
60             int ans=0;
61             for (int i=1;i<=n;i++) ans=max(ans,a[i]);
62             cout<<ans<<endl;
63     }
64 
65     return 0;
66 }

C:g挂了不少。。

x=(x*h+y)%m ;如果x已经出现，那么就有循环节。

ps:有没有循环节的可能，（被这个坑了

加入a时间是第一次到A1，并且求得周期为t1,

同理：加入b时间第一次到A2，并且求得周期为t2;

所以等式于：a+t1*x=b+t2*y;

本来这个等式可以用extendgcd求，

但我枚举周期，求得。。也比较投机了

  1 #include<stdio.h>
  2 #include<math.h>
  3 #include<algorithm>
  4 #include<string.h>
  5 #include<iostream>
  6 #include<set>
  7 #include<time.h>
  8 #include<vector>
  9 #include<map>
 10 
 11 using  namespace std;
 12 typedef long long ll;
 13 #define N 5223456
 14 #define inf 0x3f3f3f3f
 15 map<ll,int>mp;
 16 map<ll,int>mpp;
 17 
 18 int gcd(int a,int b)
 19 {
 20     if (b==0) return a;
 21     return gcd(b,a%b);
 22 }
 23 
 24 int main()
 25 {
 26 
 27     int M,H1,A1,X1,Y1,H2,A2,X2,Y2;
 28     cin>>M>>H1>>A1>>X1>>Y1>>H2>>A2>>X2>>Y2;
 29     ll tmp=H1;
 30     ll num1=0;
 31     int flag=0;
 32 
 33     for (int i=1;i<=N;i++)//N 是随便假设的，值要稍微大点
 34     {
 35         tmp=tmp*X1+Y1;
 36         tmp=tmp%M;
 37         num1++;
 38         if (tmp==A1&&!mp[tmp]) mp[tmp]=num1;
 39         else if (tmp==A1&&mp[tmp])
 40         {
 41             flag++;
 42             break;
 43         }
 44     }
 45 
 46     tmp=H2;
 47     ll num2=0;
 48     for (int i=1;i<=N;i++)
 49     {
 50         tmp=tmp*X2+Y2;
 51         tmp=tmp%M;
 52         num2++;
 53         if (tmp==A2&&!mpp[tmp]) mpp[tmp]=num2;
 54         else if (tmp==A2&&mpp[tmp])
 55         {
 56             flag++;
 57             break;
 58         }
 59     }
 60     
 61     ll tmp1=H1,tmp2=H2;
 62     int idx=0;
 63 
 64     for (int i=0;i<N;i++)
 65     {
 66           tmp1=tmp1*X1+Y1;
 67           tmp1=tmp1%M;
 68           tmp2=tmp2*X2+Y2;
 69           tmp2=tmp2%M;
 70           idx++;
 71         if (tmp1==A1&&tmp2==A2)
 72         {
 73             cout<<idx;
 74             return 0;
 75         }
 76     }
 77     
 78     if (flag<2)
 79     {
 80         cout<<-1;
 81         return 0;
 82     }
 83 
 84 
 85 
 86     ll a=mp[A1];
 87     ll b=mpp[A2];//a,b-->都是开始的时间
 88     ll c=num1-a;//c,d都是周期
 89     ll d=num2-b;
 90 
 91     for (int i=0;i<5234566;i++)//枚举周期
 92     {
 93         ll tmp=a+c*i-b;
 94         if (tmp<0) continue;
 95         if (tmp==0)
 96         {
 97             cout<<tmp+b;
 98             return 0;
 99         }
100         if (b&&tmp%d==0)
101         {
102             cout<<tmp+b;
103             return 0;
104         }
105     }
106     cout<<-1;
107 
108     return 0;
109 }

D: DSU

题意简单：对于每个i (1<=i<=n) 求长度为i 的最小值的最大。

解析：对于每个i,我们求出i 左边最大x ,使a[x]<a[i];记作 L[i];

同理我们求出右边最小x, 使a[y]<a[i],记作 R[i];那么a[r[i]-l[i]-1]=max(a[r[i]-l[i]-1],a[i]）；-->推演一下

并且 a[x]=max(a[x+1],a[x]),继续推一下，

时间复杂度O（n);

求每个L[i],R[i]用stack，单调--；

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<algorithm>
 4 #include<string.h>
 5 #include<iostream>
 6 #include<set>
 7 #include<time.h>
 8 #include<vector>
 9 
10 using  namespace std;
11 typedef long long ll;
12 #define N 1234567
13 #define inf 0x3f3f3f3f
14 
15 int mp[555][555];
16 int a[555];
17 
18 int main()
19 {
20 
21     int n,m,q;
22     cin>>n>>m>>q;
23 
24     for (int i=1;i<=n;i++)
25     for (int j=1;j<=m;j++)
26     {
27         cin>>mp[i][j];
28     }
29 
30     for (int i=1;i<=n;i++)
31     {
32         int tmp=0;
33         for (int j=1;j<=m;j++){
34         if (mp[i][j]) tmp++;
35         else tmp=0;
36         a[i]=max(a[i],tmp);
37         }
38     }
39 
40     while (q--)
41     {
42         int x,y;
43         cin>>x>>y;
44         if (mp[x][y])
45         {
46             mp[x][y]=0;
47         }
48         else
49         {
50             mp[x][y]=1;
51         }
52         a[x]=0;
53             int tmp=0;
54             for (int j=1;j<=m;j++){
55             if (mp[x][j]) tmp++;
56             else tmp=0;
57             a[x]=max(a[x],tmp);
58             }
59 
60             int ans=0;
61             for (int i=1;i<=n;i++) ans=max(ans,a[i]);
62             cout<<ans<<endl;
63     }
64 
65     return 0;
66 }