agc031

T1 题意：给你一个串，求所有子序列个数，满足没有相同字符。1e5,2s。

解：考虑一个合法的子序列。其中每个字母的出现位置都有(出现次数)种选择。还可以不选，要 + 1。

然后乘起来就做完了。如果变成子串的话更简单，每个位置为开头的长度不会超过26，直接暴力。本质不同子串就开个hash池判重。

本质不同子序列......不会。

 #include <bits/stdc++.h>

 const int N = , MO = 1e9 + ;

 char str[N];

 int bin[];

 int main() {

     int n;

     scanf("%d", &n);

     scanf("%s", str);

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

         bin[str[i] - 'a']++;

     }

     int ans = ;

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

         ans = 1ll * ans * (bin[i] + ) % MO;

     }

     printf("%d", (ans + MO - ) % MO);

     return ;

 }

AC代码

T2 题意：给你一个序列，可以若干次选择两个相同的数字，使其之间的数字全部变成这个数字。求最终可能的序列总数。2e5,2s。

解：发现选出来的序列一定是一些相离的，所以可以DP，设f[i]表示前i位可能的方案总数。那么第i位可能和前面任一个相同的数匹配，f[i] += f[j - 1]。

同时也可能不匹配，相当于自己跟自己匹配。我们要对所有ai等于一个数的DP值求和，直接开个桶。

发现有连续相同的数的时候会挂，把它们缩起来。

 #include <bits/stdc++.h>

 typedef long long LL;

 const int N = , MO = 1e9 + ;

 int a[N], bin[N], f[N];

 int main() {

     int n;

     scanf("%d", &n);

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

         scanf("%d", &a[i]);

         if(a[i] == a[i - ]) {

             i--;

             n--;

         }

     }

     f[] = ;

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

         (bin[a[i]] += f[i - ]) %= MO;

         f[i] = bin[a[i]];

     }

     printf("%d", f[n]);

     return ;

 }

AC代码

T3 题意：求一个1 ~ 2ⁿ的排列，满足第一个数是A，最后一个数是B，且相邻两个数的二进制只有一位不同。17,2s。

解：猜一下结论，如果A和B二进制下不同的位数有偶数个，那么一定无解。其余的有解。

因为有个头尾的限制，所以我们直接暴力分治。

每次讨论A和B最高位是否相同。相同的话就先把最高位变一下填2^n-1个，然后变回来填后面的。

不同的话就前2^n-1个最高位从A，后面最高位从B。

 /**

  * There is a start and there is no end in the space. ---Infinity.

  * It ruins and goes though there is also a start in stars. ---Finite.

  * Only the man who has wisdom can read the most foolish one from the history.

  * Fishes living in the sea doesn't know the life in the land.

  * It also ruins and goes if they have wisdom.

  * It funnier that man exceeds the speed of light than fish start living in the land.

  * It can be said that this is an final ultimatum from the god to the people who can fight.

  *

  * Steins;Gate

  */

 #include <bits/stdc++.h>

 const int N = ;

 int n, A, B, p[N], top, now, lm, same, dt;

 inline void out(int x) {

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

         printf("%d", (x >> i) & );

     }

     return;

 }

 inline int cal(int x) {

     int ans = ;

     while(x) {

         ans++;

         x -= x & (-x);

     }

     return ans;

 }

 inline int Abs(int x) {

     return x <  ? -x : x;

 }

 inline int First(int x) {

     for(int i = n - ; i >= ; i--) {

         if((x >> i) & ) return  << i;

     }

     return ;

 }

 void solve(int n, int l, int r, int a, int b) {

     if(n == ) {

         p[l] = a;

         p[r] = b;

         return;

     }

     int mid = (l + r) >> , nexlm = ( << (n - )) - ;

     if(((a >> (n - )) & ) == ((b >> (n - )) & )) {

         solve(n - , mid + , r, a & nexlm, b & nexlm);

         if((a >> (n - )) & ) {

             for(int i = mid + ; i <= r; i++) {

                 p[i] |=  << (n - );

             }

             p[l] = p[mid + ];

             solve(n - , l + , mid + , a & nexlm, p[mid + ] & nexlm);

         }

         else {

             p[l] = p[mid + ];

             solve(n - , l + , mid + , a & nexlm, p[mid + ] & nexlm);

             for(int i = l + ; i <= mid + ; i++) {

                 p[i] |= ( << (n - ));

             }

         }

     }

     else {

         solve(n - , l, mid, a & nexlm, (b & nexlm) ^ );

         if((a >> (n - )) & ) {

             for(int i = l; i <= mid; i++) {

                 p[i] |=  << (n - );

             }

             solve(n - , mid + , r, p[mid] & nexlm, b & nexlm);

         }

         else {

             solve(n - , mid + , r, p[mid] & nexlm, b & nexlm);

             for(int i = mid + ; i <= r; i++) {

                 p[i] |=  << (n - );

             }

         }

     }

     return;

 }

 int main() {

     scanf("%d%d%d", &n, &A, &B);

     lm = ( << n) - , dt = A ^ B, same = dt ^ lm;

     if((cal(dt) & ) == ) {

         puts("NO");

     }

     else {

         puts("YES");

         solve(n, , lm, A, B);

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

             //out(p[i]); printf(" ");

             printf("%d ", p[i]);

             //puts("");

         }

     }

     return ;

 }

AC代码

T4 题意：给定两个排列a和b，定义f(a, b)是一个排列，满足第a_i个位置上的数是b_i。定义A为一个序列，每个元素是一个排列，且A₁ = a, A₂ = b, A_i = f(A_i-2, A_i-1)，求A_k。10w,1e9,2s。

解：神仙...

对于两个排列a和b，定义ab[i] = a[b[i]], a^-1[a[i]] = i。于是我们把A的前几项写出来，然后瞎搞一通，就能发现一个奇妙的规律orz...

直接上官方题解了。

我们把A的每一个元素拆成sts^-1的形式。然后发现s_i+6 = s_iba^-1b^-1a，是个等比数列。然后t是6个一循环的。

于是我们求出ba^-1b^-1a的k / 6次方就做完了......注意到求一个排列的k次方只需找出每个元素所在的环，然后跳(k % 环长)步即可。

 #include <bits/stdc++.h>

 const int N = ;

 int a[N], b[N], c[N], d[N], A[N], n, k, vis[N], B[N], dis[N], C[N], D[N];

 int t1[][N], t2[][N], t3[][N], ans[][N];

 std::vector<int> v[N];

 inline int Find(int x, int t) {

     int loop = v[vis[x]].size() - ;

     t = (t + dis[x]) % loop;

     return v[vis[x]][t];

 }

 int main() {

     scanf("%d%d", &n, &k);

     k--;

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

     for(int i = ; i <= n; i++) scanf("%d", &b[i]);

     /// get A  c = b-1  d = a-1

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

         c[b[i]] = i;

         d[a[i]] = i;

     }

     /*for(int i = 1; i <= n; i++) {

         printf("%d ", c[i]);

     }

     puts("");

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

         printf("%d ", d[i]);

     }

     puts("");*/

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

         A[i] = b[d[c[ a[i] ]]];

     }

     int t = k / ;

     //printf("t = %d \n", t);

     /// get B = A^t

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

         if(vis[i]) continue;

         /// !vis[i]

         int j = i;

         v[i].push_back(i);

         do {

             j = A[j];

             dis[j] = v[i].size();

             vis[j] = i;

             v[i].push_back(j);

         } while(j != i);

         dis[i] = ;

     }

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

         B[i] = t ? Find(i, t) : i;

     }

     /*printf("vis : \n");

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

         printf("%d ", vis[i]);

     }

     puts("");

     printf("A : \n");

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

         printf("%d ", A[i]);

     }

     puts("");*/

     memcpy(t1[] + , B + , n * sizeof(int));

     memcpy(t1[] + , B + , n * sizeof(int));

     memcpy(t2[] + , a + , n * sizeof(int));

     memcpy(t2[] + , b + , n * sizeof(int));

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

         t3[][t1[][i]] = i;

         t3[][t1[][i]] = i;

     }

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

         ans[][i] = t1[][t2[][t3[][i]]];

         ans[][i] = t1[][t2[][t3[][i]]];

     }

     t = k % ;

     //printf("t = %d \n", t);

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

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

             ans[i][ans[i - ][j]] = ans[i - ][j];

         }

     }

     /*puts("");

     for(int i = 0; i <= 1; i++) {

         for(int j = 1; j <= n; j++) {

             printf("%d ", ans[i][j]);

         }

         puts("");

     }

     puts("");*/

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

         printf("%d ", ans[t][i]);

     }

     return ;

 }

AC代码

巴特西

agc031

最新文章

热门文章