CF1305 简要题解（A ~ F）

场上总是想到鸡肋做法写好久啊。。CF好难 /dk

A Kuroni and the Gifts

注意到数字不同，排序后输出就好了，匹配必然是递增的。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 200006
int n , m;
int A[MAXN] , B[MAXN];

int main() {
    int T;cin >> T;
    while( T-- ) {
        scanf("%d",&n);
        for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]);
        for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&B[i]);
        sort( A + 1 , A + 1 + n ) , sort( B + 1 , B + 1 + n );
        for( int i = 1; i <= n ; ++ i ) printf("%d ",A[i]);
        puts("");
        for( int i = 1; i <= n ; ++ i ) printf("%d ",B[i]);
        puts("");
    }
}

B Kuroni and Simple Strings

贪心一下，最后删掉的必然是一段前缀中的所有 ( 和一段后缀中的所有 ) 并且没有交，所以直接枚举删除的匹配的 () 的个数就好了。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
using namespace std;
#define MAXN 200006
int n , m;
int A[MAXN] , B[MAXN];
char ch[MAXN];
vector<int> ans;
int main() {
    scanf("%s",ch);
    n = strlen( ch );
    int flg = 0;
    for( int k = 1 ; k <= n / 2 ; ++ k) {
        int i , c = k;
        ans.clear();
        memset( B , 0 , sizeof B );
        for( i = 0 ; i < n ; ++ i ) {
            if( ch[i] == '(' ) B[i] = 1 , -- c , ans.push_back( i );
            if( !c ) break;
        }
        if( c ) { flg = 1; break; }
        c = k;
        for( int j = n - 1 ; j > i ; -- j ) {
            if( ch[j] == ')' ) B[j] = 1 , -- c , ans.push_back( j );
            if( !c ) break;
        }
        if( c ) { flg = 1; break; }
        int tr = 0;
        for( int i = 0 ; i < n ; ++ i ) {
            if( B[i] ) continue;
            if( ch[i] == '(' ) {
                if( !tr ) tr = 1;
            } else {
                if( tr ) { tr = 2; break; }
            }
        }
        if( tr == 2 ) continue;
        else {
            puts("1");
            sort( ans.begin() , ans.end() );
            printf("%d\n",ans.size());
            for( int i : ans ) printf("%d ",i + 1);
            break;
        }
    }
    if( flg ) puts("0");
}

C Kuroni and Impossible Calculation

考虑当 $n > m$ 的时候必然无解。显然，如果有模意义下重复数字无解。否则，我们相当于开 $m$ 个桶，然后会发现桶里不能有重复数字。于是显然成立。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
#include "map"
using namespace std;
#define int long long
#define MAXN 200006
int n , m;
int A[MAXN];
int buc[1006];
inline long long ab( long long a ) {
    return a > 0 ? a : -a;
}
signed main() {
    scanf("%d%d", &n, &m);
    if( n > 2000 ) return puts("0") , 0;
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    int res = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++) res = ab(A[i] - A[j]) * res % m;
    cout << res << endl;
}

D Kuroni and the Celebration

场上做法过于复杂不说了。。

每次选择两个叶子，也就是按照拓扑序来做，我们知道一棵树必然会有至少两个叶子。。

而且我们知道如果根是这两个叶子之一显然会直接出这两个叶子之一。于是我们顺利排除了两个点。

所以最后我们用了不超过 $\lfloor \frac n 2 \rfloor$ 次操作就必然可以找到根。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 1006
int n;
int deg[MAXN] , don[MAXN];
vector<int> G[MAXN];
int main() {
    cin >> n;
    for( int i = 1 , u , v ; i < n ; ++ i ) {
        scanf("%d%d",&u,&v);
        G[u].push_back( v ) , G[v].push_back( u );
        ++ deg[u] , ++ deg[v];
    }
    queue<int> Q;
    for( int i = 1 ; i <= n ; ++ i ) if( deg[i] == 1 ) Q.push( i );
    int cn = n;
    while( cn > 1 ) {
        int t = Q.front(); Q.pop(); int p = Q.front(); Q.pop();
        printf("? %d %d\n",t,p); fflush( stdout );
        int r;
        scanf("%d",&r);
        if( r == t ) { printf("! %d\n",r);fflush(stdout); return 0; }
        if( r == p ) { printf("! %d\n",r);fflush(stdout); return 0; }
        don[t] = don[p] = 1;
        cn -= 2;
        for( int v : G[t] ) {
            -- deg[v];
            if( deg[v] == 1 ) Q.push( v );
        }
        for( int v : G[p] ) {
            -- deg[v];
            if( deg[v] == 1 ) Q.push( v );
        }
    }
    for( int i = 1 ; i <= n ; ++ i ) if( !don[i] ) { printf("! %d\n",i); fflush( stdout ); return 0; }
}

E Kuroni and the Score Distribution

开始没看到不能有重复数字啊啊。。。。。。

于是由于不能有重复数字，我们知道最优方案一定是 $1,2,3,4,5,\dots,n$ 至于为啥，可以假设中间断开了，显然不会优秀于不断开的情况，推广一下就有了这个结论。

所以我们可以先 $1,2,3,\dots,k$ 构造，考虑加入下一个就会导致超过 $m$ 的时候，就把下一个尝试放 $k+1,k+2,\dots ,k+n$ 必然可以找到一个满足正好为 $m$ 的值。因为每两个正好可以让个数下降 1。

后面就从一个很大的数开始每次 + 10000 就好了。

#include <iostream>
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
#include "map"
using namespace std;
#define MAXN 5006
int n , m;
int A[MAXN];
vector<int> ans;
int main() {
    cin >> n >> m ;
    int c = 0 , r = 0;
    for( int i = 1 ; i <= n ; ++ i ) {
        if( ( i - 1 ) / 2 + c >= m ) {
            for( int j = i ; ; ++ j ) {
                if( ( ( i - 1 ) - ( j - i ) ) / 2 + c == m ) {
                    for( int k : ans ) printf("%d ",k) , ++ r;
                    printf("%d ",j) , ++ r;
                    int t = 400000000;
                    for( int i = r + 1 ; i <= n ; ++ i ) {
                        printf("%d ",t) , t += 10000;
                    }
                    return 0;
                }
            }
        } else {
            c += ( i - 1 ) / 2;
            ans.push_back( i );
        }
    }
    puts("-1");
}

考虑随机20个数，然后把它们 +- 1…3 全部分解质因数。这样做的正确率是什么呢？由于我们知道答案的上界是 $n$ 级别的，因为你选择 2 需要的步骤最多就是 $n$ 。于是最多不超过 $\frac n 4$ 个数字改变次数超了 4 。所以随机一次拿到一个需要改变次数不超过 4 的数字概率是 $\frac 1 4$ 于是最终正确率是 $1 - {\frac 1 4}^{20}$ 显然几乎 $100\%$ 正确。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include "random"
#include "chrono"
using namespace std;
#define MAXN 200006
#define int long long
int n;
int A[MAXN];
mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int rnd( ) {
    return rand();
}
vector<int> divs;
void analyze( int x ) {
    if( x < 2 ) return;
    int c = x;
    for( int i = 2 ; i * i <= x ; ++ i ) if( c % i == 0 ) {
        while( c % i == 0 ) c /= i;
        divs.push_back( i );
    }
    if( c != 1 ) divs.push_back( c );
}
int ans = 0x3f3f3f3f;
void chkans( int x ) {
    int re = 0;
    for( int i = 1 ; i <= n ; ++ i )
        re += min( x - A[i] % x , A[i] >= x ? A[i] % x : 0x3f3f3f3f );
    ans = min( ans , re );
}

signed main() {
    srand( Rnd( ) );
    cin >> n;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&A[i]);
    for( int t = 1 ; t <= 20 ; ++ t ) {
        for( int q = -3 ; q <= 3 ; ++ q )
            analyze( A[rnd() % n + 1] + q );
    }
    sort( divs.begin() , divs.end() );
    divs.erase( unique( divs.begin() , divs.end() ) , divs.end() );
    for( int i : divs )
        chkans( i );
    cout << ans << endl;
}