2018 CCPC桂林H,J 2019ICPC 台北H J

这场nice，一个签到，三个铜牌题做出，铜牌题做两个就有铜了。

但是除了读题基本0贡献了，签到的活被抢了，G完全没参与，H想好思路之后居然写挂了。

J（博弈）

之前做过一个题是确定最终状态，由于真的长得很像，所以一开始我们也去搞确定最终状态去了，实际上只需对于每一堆石头反复的贪心抓取即可。

对于a[i]这个位置，这一轮可以抓取的个数分三个情况

1.a[i]小于两边，可以一直抓到0
2.a[i]大于一边，可以抓到那边的a[j]+1
3.大于两边，可以抓到两边的最大值的+1

换句话来说，就是只要不和两边相等，我就可以尽量往小里抓。

复杂度不太会证明，但是据说是2n

#include 

using namespace std;
#define int long long
#define endl '\n'

const int N = 1e5+1000;
int a[N];

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    int cnt=0;
    for(cin>>t;t;t--)
    {
        cnt++;
        int n;
        cin>>n;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        int x=1;
        a[0]=a[n+1]=1e9+100;
        while(x)
        {
            x=0;
            for(int i=1;i<=n;i++)
            {
                int m=-1;
                if(a[i]>a[i-1])
                    m=max(m,a[i-1]);
                if(a[i]>a[i+1])
                    m=max(m,a[i+1]);
                x+=a[i]-m-1;
                a[i]=m+1;
            }
            sum+=x;
        }
        if(sum&1)
        {
            cout<<"Case "<<cnt<<": "<<"Alice";
        }
        else
        {
            cout<<"Case "<<cnt<<": "<<"Bob";
        }
        if(t!=1)
            cout<<endl;
    }
    return 0;
}
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

H. Hamming Distance（贪心，思维）

思路：确定的思路是：目前即将要更换的位置，我们希望的换的字母在满足答案最终状态合法的情况下字典序最小，
ca和cb这两个串来讲
我们第一位显然用‘a’即可，但是对于第二位，如果我们用a，则会产生一个差值，使得目标串ans和ca与cb的距离不一样，那么什么时候我们又可以选呢？

cab
cba
这种情况下，在第二位之后还有位置是不相等的，这时我们可以把这个代价（差值延后）到最后一位上。

ans就是aaa

sum后缀记录不同个数的前缀和。

然后对于每一位要换的字母都从26个字母里枚举。（nnd，我一开始写的是精确判断，挂了，队友写个枚举过了，而且还飞快）

#include
#define endl '\n'
#define int long long
using namespace std;
const int N=2e6+5;
int t,sum[N];
char s[N],e[N],ans[N];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    int ca=0;
    while(t--)
    {
        cin>>(s+1)>>(e+1);
        int n=strlen(s+1);sum[n+1]=0;
        for(int i=n;i>=1;i--)
        {
            sum[i]=sum[i+1]+(s[i]!=e[i]);
        }
        int disa=0,disb=0;
        for(int i=1;i<=n;i++)
        {
            for(char j='a';j<='z';j++)
            {
                int da=disa,db=disb;
                if(s[i]!=j) da++;
                if(e[i]!=j) db++;
                if(abs(da-db)>sum[i+1]) continue;
                ans[i]=j;
                disa=da;disb=db;
                break;
            }
        }
        cout<<"Case "<<++ca<<": ";
        for(int i=1;i<=n;i++) cout<<ans[i];
        cout<<endl;
    }
    return 0;
}
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

2019台北
H（找规律）

题目要求满足的式子来推导，但是发现没有什么结果啊，根据题目给出的大量的样例提示，试着找了一个规律
：b必然是n+1。

此时一个仅包含未知量a的一元一次不等式就已经浮现了，那么直接解出即可。

#include 
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5+1000;
const int mod = 1e9+7;
int t,n,a[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        cout<<((n*(n+1ll))^(n+1ll))<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

J - Automatic Control Machine

按照题目中描述的，这个是一个小规模下的可重覆盖问题，原本我想用DLX直接碾压过去，结果发现我只整理的精确覆盖问题，，

#include 
#define endl '\n'
#define int long long
using namespace std;
const int inf=1e18;
const int N = 1000;
int t,n,m,cnt[N],ans;
char s[20][N];
vector<int>g[20];
void dfs(int pos,int num,int res)
{
    if(ans<=res) return;
    if(num==n){ans=res;return;}
    for(int i=pos+1;i<=m;i++)
    {
        int tmp=num;
        for(auto x:g[i])
        {
            if(cnt[x]<=0) tmp++;
            cnt[x]++;
        }
        dfs(i,tmp,res+1);
        for(auto x:g[i])
            cnt[x]--;
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cnt[i]=0,g[i].clear();
        for(int i=1;i<=m;i++)
        {
            cin>>(s[i]+1);
            for(int j=1;j<=n;j++)
            {
                if(s[i][j]=='1') cnt[j]++,g[i].push_back(j);
            }
        }
        int flag=1;
        ans=inf;
        for(int i=1;i<=n;i++)
        {
            if(cnt[i]<=0){flag=0;break;}
            cnt[i]=0;
        }
        if(!flag){cout<<"-1\n";continue;}
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}

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

牛客小白62 E（离线，lazytag思想）

还是挺巧妙的，题目给的所有操作可以转化为差分，利用差分数组存好之后再利用类似于lazytag的思想去做传递，可以视为一个自顶向下离线方式利用lazytag的过程。

#include 
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e7+100;
int a[N];
int n,m;
int num1[N];
int vis[N];
void DFS(int p,int x)
{
    if(p>n)
        return;
    a[p]+=x;
    DFS(p*2,x+num1[p*2]);
    DFS(p*2+1,x+num1[p*2+1]);
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int op,x;
        cin>>op;
        if(op==1)
        {
            cin>>x;
            num1[x]++;
        }
        if(op==2)
        {
            cin>>x;
            num1[1]++;
            num1[x]--;
        }
        if(op==3)
        {
            cin>>x;
            while(x)
            {
                a[x]++;
                x/=2;
            }
        }
        if(op==4)
        {
            cin>>x;
            while(x)
            {
                a[x]--;
                x/=2;
            }
            num1[1]++;
        }
    }
    DFS(1,num1[1]);
    for(int i=1;i<=n;i++)
        vis[a[i]]++;
    for(int i=0;i<=m;i++)
        cout<<vis[i]<<" ";
    return 0;
}

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

好累啊，，今天先到这里吧