Bobo String Construction

题目大意

给定一个数和字符串，让你构造一个，使得连成后，除了头尾两个子串t以外不会出现子串为的情况（可以重叠）

解题思路

先说结论，s全为0和全为1一定有一个符合条件。

不合法的构造会是下面三种情况，

①单看s串中出现了子串t

②s的前缀与t的后缀构成了t

③s的后缀与t的前缀构成了t

如果是情况①，全0和全1两种构造显然不可能和t都相同。

如果是情况②和情况③，s的前缀或后缀为什么时才与t的前缀或后缀构成了t。

例如情况②，t为10010时，与t的后缀产生不合法情况时s的前缀为010，思考也容易想到这与t的相等前后缀有关。t的前缀10和后缀10相等，所以s的前缀为t前缀后面的部分010时会出现了t，同理s的后缀不能为t的相等前后缀中后缀前面的部分100，这两个是否可能出现一个全1一个全0，当两部分有公共部分时，显然不可能。若无公共部分，假设字符串t：abcde，前后缀分别为abc和cde相等，那么a等于c，c等于e，无论如何构造为满足前后缀相等的前提，这两个部分就一定不可能都不同即一个全0，一个全1的情况。

并且情况①和②③显然出现一个全0，一个全1，因为②③中的t与①中的t相同。

如此而言，我们只需分别判断全0和全1时是否合法选择合法的情况输出即可。

时间复杂度：

我用kmp做的，其实不用kmp，直接暴力nm复杂度也可以过

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
bool multi=1;
const int N=3010;
int n;
char t[N];
char s[N];
int ne[N];
vector<int> res;

void solve(){
    res.clear();
    cin>>n;
    cin>>t+1;
    int m=strlen(t+1);
    for(int i=1;i<=m;i++){
        s[i]=t[i];
        s[i+m+n]=t[i];
    }
    int tot=m*2+n;
    s[tot+1]=0;
    memset(ne,0,(tot+1)*sizeof(int));
    for(int i=m+1;i<=m+n;i++){
        s[i]='1';
    }

//kmp判断是否合法
    //求ne的过程
    int i=0,j=0;
    for(i=2,j=0;i<=m;i++){
        while(j&&t[i]!=t[j+1]){
            j=ne[j];
        }
        if(t[i]==t[j+1]) j++;
        ne[i]=j;
    }

    //kmp的匹配过程，将所有模式串在主串出现位置的起始下标保存在res中
    for(i=1,j=0;i<=tot;i++){
        while(j&&s[i]!=t[j+1]){
            j=ne[j];
        }
        if(s[i]==t[j+1]) j++;
        if(j==m){
            res.push_back(i-m);
            j=ne[j];//为了观察其后续是否还能跟S数组后面的数配对成功
        }
    }
    if((int)res.size()!=2){//若res数量为两个即找到两个子串，则是开头结尾两个符合题意。
        for(int i=m+1;i<=m+n;i++){
            s[i]='0';
        }
        for(int i=1;i<=n;i++){
            cout<<0;
        }
        cout<<endl;
    }else{
        for(int i=1;i<=n;i++){
            cout<<1;
        }
        cout<<endl;
    }

}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Election of the King

题目大意

有n个候选人选举国王，共n-1轮投票，每轮每人会投离自己政治倾向数值差值最大的那个人，如果有多个则投较大的那个人，一轮中被投票最多的人被淘汰，最终谁会当上国王。

解题思路

显然，若将每个人按照政治倾向排序，每轮被淘汰的人只会是政治倾向最小或最大的，因此我们可以用双指针，一个指向最小，一个指向最大，每轮O(1)判断出最小还是最大的淘汰往中间移动指针。

如何O(1)判断最小的被投票还是最大的被投票？

当剩下人数为奇数时，由于集合有序，若最中间的人投向最大那么其左边的一定投向最大，否则中间即右边的都投向最小。

当剩下人数为偶数时，同理，这时我们只需要看中间的两个中左边那个，若他投向最右边那么有一半的人都投向最右，右边指针左移，反之亦然。

时间复杂度:O(n)

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
bool multi=0;
int n;
const int N=1e6+10;
PII a[N];

void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].first;
        a[i].second=i+1;
    }
    sort(a,a+n);
    int l=0,r=n-1;
    while(l<r){
        if((l+r)%2==0){
            if(a[r].first-a[(l+r)/2].first>=a[(l+r)/2].first-a[l].first){
                r--;
            }else{
                l++;
            }
        }else{
            if(a[r].first-a[(l+r)/2].first>=a[(l+r)/2].first-a[l].first){
                r--;
            }else{
                l++;
            }
        }
    }
    cout<<a[l].second<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Merge the squares!

题目大意

给定一个个变成为1的小正方形，每次可以将2到50个正方形合并成一个大正方形，求合并成一个大正方形的方案。

解题思路

对于一个正方形，若它的边长小于等于7，直接合并，否则分割成两个正方形和两个长方形，其长方形的长和宽先预处理使得长方形分割完后数量不超过24个，因为最后合并需要24+24+两个正方形。

如何预处理，一个长方形可以每次切割它最大的边长，这里就变成了类似求gcd的辗转相减可以快速求出一个长方形切割到最后有多少个cnt，我们可以枚举这个长方形的边长，满足

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'

bool multi=0;

struct Node{
    int x, y, w;
};

const int N=1010;
int sp[N];
vector<Node> ans;

void solve(int x, int y, int a, int b){
    if(a == b){
        if(a == 1) return;
        else if(a <= 7){//边长小于等于7的正方形，直接合并。
            ans.push_back({x, y, a});
            return;
        }
        solve(x, y, sp[a], a);//将正方形切割成两个小长方形
        solve(x + sp[a], y, a - sp[a], a);
        ans.push_back({x, y, a});
        return;
    }
    if(a > b){//每次截取一个长方形中最大的正方形
        solve(x, y, b, b);
        solve(x + b, y, a - b, b);
    }else{//每次截取一个长方形中最大的正方形
        solve(x, y, a, a);
        solve(x, y + a, a, b - a);
    }
}

void solve(){
    int n;
    cin >> n;
    solve(1, 1, n, n);
    cout << ans.size() << '\n';
    for(auto it: ans) cout << it.x << ' ' << it.y << ' ' << it.w << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    for(int i = 2; i <= 1000; i ++){
        //预处理一个正方形切成怎样的两个小正方形可以使得最终合并块数不多于24
        for(int j = 1; j < i; j ++){
            int a = max(j, i - j), b = min(j, i - j), cnt=0;
            while(b>0){
                cnt += a / b;
                a %= b;
                swap(a, b);
            }
            if(cnt <= 24){
                sp[i]=j;
                break;
            }
        }
    }

    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Qu’est-ce Que C’est?

题目大意

构造一个长度为n的数列，其中每个数的范围都在之间，求使得这个数列满足每个长度大于等于2的连续子序列之和非负的方案数。

解题思路

令为取到第i位的最小后缀和j的合法方案数，由于这里是长度大于等于2的连续子序列之和非负，所以第i位为负数不一定非法，j可以为负数。

当第i位为负数时，即j就是这个负数，因为i-1位不可能小于0，否则序列非法，不能转移。那么此时从选到i-1位中为-j ~ m转移过来。

若非负，则从i-1时的-m+j ~ m转移。

可以发现转移的都是一段连续区间，加上前缀和优化。

空间较大，这里采用滚动数组。

时间复杂度：

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
bool multi=0;
int n,m;
const int N=5010,M=N*2;
int dp[2][M];
const int mod=998244353;
void solve(){
    cin>>n>>m;
    for(int i=-m;i<=m;i++){
        dp[1][i+N]=i+m+1;
    }
    for(int i=2;i<=n;i++){
        for(int j=-m;j<=m;j++){
            if(j<0) dp[i&1][j+N]=(dp[(i-1)&1][m+N]-dp[(i-1)&1][-j-1+N]+mod)%mod;
            else dp[i&1][j+N]=(dp[(i-1)&1][m+N]-dp[(i-1)&1][-m-1+j+N]+mod)%mod;
        }
        for(int j=-m;j<=m;j++) dp[i&1][j+N]=(dp[i&1][j+N]+dp[i&1][j-1+N]+mod)%mod;
    }
    cout<<dp[n&1][m+N]<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

We are the Lights

题目大意

有n行m列的灯，刚开始这些灯都是关的，接下来有q次操作，每次操作可能是关或开某一列或某一行的灯，问你最后有多少灯开着。

解题思路

由于最终每盏灯的状态必然与最后一次操作到的情况一致，因此我们存储所有操作倒着遍历：

若操作的那行或那列已经被操作过了，直接跳过。

否则，

首先我们初始答案为0，即全关状态。

例如对第x行进行开灯操作，我们只需要让答案加上一行内的总数，然后减去列操作的数量，在列操作中有两种情况，要么固定那一行一定全开，这里已经算过开灯数量的贡献，要么固定那一行一定全关，之后再对行进行开灯操作自然不需要算上这些一定关的灯。同时还要记录对这个行已经操作过。

如果是对第x行进行关灯操作，由于初始答案为关灯数，并无对答案的贡献，但同样需标记这行已经被操作过。

对列操作同理。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
bool multi=0;
int n,m,qq;
const int N=1e6+10;
struct Node{
    bool rc;
    int pos;
    bool op;
}q[N];

int str[N],stc[N];
//str为行状态，stc为列状态

void solve(){
    cin>>n>>m>>qq;
    //最初每行列状态都未确定。
    for(int i=1;i<=n;i++){
        str[i]=-1;
    }
    for(int i=1;i<=m;i++){
        stc[i]=-1;
    }
    int res=0;
    for(int i=0;i<qq;i++){//先把操作都都读进来，离线处理。
        string pos;
        cin>>pos;
        int idx;
        cin>>idx;
        string op;
        cin>>op;
        q[i].rc=(pos=="column");
        q[i].pos=idx;
        q[i].op=(op=="on");
    }
    map<int,bool> ron,con,rof,cof;//记录对第几行或第几列进行开灯或关灯的状态。
    for(int i=qq-1;i>=0;i--){//倒着遍历
        int rc=q[i].rc,pos=q[i].pos,op=q[i].op;
        if(rc&&stc[pos]==-1){//列操作，且该列位被操作过，若已被操作过直接continue
            stc[pos]=op;
            if(op){
                res+=n-(int)rof.size()-(int)ron.size();//减去已经固定了多少行的状态
                con[pos]=true;
            }else{
                cof[pos]=true;
            }
        }else if(!rc&&str[pos]==-1){
            str[pos]=op;
            if(op){
                res+=m-(int)cof.size()-(int)con.size();
                ron[pos]=true;
            }else{
                rof[pos]=true;
            }
        }
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}