省常中 Day 3

我只想打游戏啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

去打游戏。

今天的题目偏难，于是陷入了啥也不会的境地。

T1

赛时基本上想出正解所以拿了90pts。但是由于对字符串长度越界的情况没有处理好掉了一个点。

思路大致是求每个 $si的长度，并通过其长度对应s{i-1}与s_{i-2}中s_i的第k$ 个字符的位置。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,k,f[N],idans;
char s[3][30];
signed main()
{
    scanf("%s%s",s[1]+1,s[2]+1);
    scanf("%lld%lld",&n,&k);
    if (n<=2){
        printf("%c",s[n][k]);
        return 0;
    }
    f[1]=strlen(s[1]+1);
    f[2]=strlen(s[2]+1);
    idans=n;
    for (int i=3;i<=n;i++){
        f[i]=min(k+1,f[i-1]+f[i-2]);
    }
    while (idans>2){
        if (k<=f[idans-2]){
            idans-=2;
        }
        else{
            k-=f[idans-2];
            idans--;
        }
    }
    printf("%c",s[idans][k]);
    return 0;
}

T2

赛时试图利用类似并查集求最小环的解法，但是这个解法很容易被证伪。最后拿了15pts。

正解是通过三角形总数减去边不同色的三角形得到边同色的三角形。主要用到了一些离奇的小学数学（

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=8005;
int n,seed,d[N],sum;
bool e[N][N];
void GENERATE(){ //在生成数据的同时统计
    mt19937 gen(seed); 
    for (int i=0;i<n;i++){   
        for (int j=i+1;j<n;j++){    
            e[j][i]=e[i][j]=gen()&1;
            if (e[i][j]){
                d[i]++;
                d[j]++;
            }
        }  
    }  
    return;
}
signed main()
{
    scanf("%lld%lld",&n,&seed);
    GENERATE();
    for (int i=0;i<n;i++){
        sum+=d[i]*(n-1-d[i]);
    }
    sum/=2;
    printf("%lld",n*(n-1)*(n-2)/6-sum);
    return 0;
}

感觉T3和T4还是很抽象，我明早再看看回放。

感觉累。