A

输出 YES。

考虑 Probability Method，我们以 $50\%$ 的概率独立均匀随机每个点是农业城市还是工业城市，一条边成为好边的概率就是 $\frac{1}{2}$，那么期望边数就是 $\frac{m}{2}$，所以一定存在一种方案边数 $>\frac{m}{2}$。

出题人比较毒瘤，说 $m$ 是正整数结果数据有 $m=0$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

int main(){
    int m;scanf("%*d%d",&m);
    puts(m?"Yes":"No");
    return 0;
} 

B

不会。。感觉比 T3 还难，就差一步就想出来了。

首先我们发现操作可逆，我们还可以对于一个位置 $p$，找到前面连续的一段长度为 $k$ 的相同区间，将一个数往前移动 $k$ 位。所以我们可以找出 $s$ 内所有相同的长度为 $k$ 的区间扔到最后面（也就是删除），对 $t$ 也这样做，然后判断是否相等即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
int n,k;

inline void f(char str[],char res[],int &tp){
    static int len[MAXN],t[MAXN];
    tp = 0;t[0] = -1;len[0] = 0;
    FOR(i,1,n){
        ++tp;res[tp] = str[i];
        if(str[i]-'a' == t[tp-1]){
            len[tp] = len[tp-1]+1;
            t[tp] = t[tp-1];
        }
        else{
            len[tp] = 1;
            t[tp] = str[i]-'a';
        }
        while(tp > 0 && len[tp] == k) tp -= k;
    }
    // DEBUG(tp);
}

char s[MAXN],t[MAXN];
char ts[MAXN],tt[MAXN];

inline void Solve(){
    scanf("%d%d",&n,&k);
    scanf("%s%s",s+1,t+1);
    int t1=0,t2=0;
    f(s,ts,t1);f(t,tt,t2);
    bool flag = t1==t2;
    FOR(i,1,t1) flag &= (ts[i]==tt[i]);
    puts(flag?"Yes":"No");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

C

至少包含两条形如 $x \in S$ 的信息，随便找两个 $x,y$ 一定存在 $S$ 内的信息，求个差 $d=x-y$，发现可能的公差只可能是 $d$ 的因子。

然后枚举公差后我们唯一可做的是删除一些前缀和后缀，每个限制形如你至少要删除一段前后缀/至少要保留一段前后缀，如果能算出来前后缀最多/最少能保留多少，就可以用乘法原理算出答案了。

直接做是 $O(md)$ 的，看起来很没道理。但是我们发现对于一个限制数 $v$，和它有关系的 $d$ 当且仅当 $(v-x)|d$，我们可以先求 $g=\gcd(v-x,d)$，容易发现 $g|d$，所以预处理所有因子的因子，直接把限制挂上去就行了。复杂度 $O(d^2)$。

/*
这怎么对拍啊？？？答案全是0
能过算我输 
*/ 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int ha = 1e9 + 7;
const int MAXN = 2e5 + 5;
LL n;int m;
std::vector<LL> v0,v1;
std::vector<LL> dec;
std::vector<LL> G[MAXN];
std::vector<LL> lim0[MAXN],lim1[MAXN];
LL x,y,d;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

inline int work(int id){
    d = dec[id];
    LL k = (n-y)/d;
    LL mx = y+k*d;
    k = (x-1)/d;
    LL mn = x-d*k;
//    DEBUG(d);//DEBUG(mn);DEBUG(mx);
    for(auto &x:lim0[id]) x = 1+(x-mn)/d;
    for(auto &x:lim1[id]) x = 1+(x-mn)/d;
    if(lim1[id].size() != (int)v1.size()-2) return 0;
    mx = 1+(mx-mn)/d;
    LL xx = 1+(x-mn)/d,yy = 1+(y-mn)/d;
    LL l0 = 0,r0 = mx+1;
    for(auto x:lim0[id]){
        if(x < xx){
            l0 = std::max(l0,x);
        }
        else if(x > yy){
            r0 = std::min(r0,x);
        }
        else return 0;
    }
    LL l1 = xx,r1 = yy;
    for(auto x:lim1[id]){
        if(x < xx){
            l1 = std::min(l1,x);
        }
        else if(x > yy){
            r1 = std::max(r1,x);
        }
        else{
            continue;
        }
    }
    if(l1-l0 < 0 || r0-r1 < 0) return 0;
//    DEBUG((l1-l0)*(r0-r1));
    return 1ll*(l1-l0)%ha*(r0-r1)%ha;
}

inline LL gcd(LL a,LL b){
    return !b ? a : gcd(b,a%b);
}

inline LL abs(LL x){
    if(x < 0) return -x;
    return x;
}

int main(){
    read(n);read(m);
    FOR(i,1,m){
        int opt;LL x;read(opt);read(x);
        if(opt == 0) v0.pb(x);
        else v1.pb(x);
    }
    std::sort(all(v0));std::sort(all(v1));
    x = v1[0],y = v1[1],d = y-x;
    LL q = std::sqrt(1.0*d);
    FOR(i,1,q){
        if(!(d%i)){
            dec.pb(i);
            if(1ll*i*i != d) dec.pb(d/i);
        }
    }
    std::sort(all(dec));
    int m = dec.size();
    FOR(i,0,m-1){
        FOR(j,0,i){
            if(dec[i]%dec[j] == 0) G[i].pb(j);
        }
    }
    for(auto v:v0){
        LL g = gcd(abs(x-v),d);
        int p = std::lower_bound(all(dec),g)-dec.begin();
        for(auto x:G[p]) lim0[x].pb(v);
    }
    for(auto v:v1){
        if(v == x || v == y) continue;
        LL g = gcd(abs(x-v),d);
        int p = std::lower_bound(all(dec),g)-dec.begin();
        for(auto x:G[p]) lim1[x].pb(v);
    }
    int ans = 0;
    FOR(i,0,m-1) (ans += work(i)) %= ha;
    printf("%d\n",ans);
    return 0;
}