Codeforces Round #832 (Div. 2)C,D ICPC澳门 D(模拟) F(构造) G(博弈）

前两天vp的济南没啥好写的啊，，没有我的知识点，小难受

澳门的这三个题都不错，div2的D不错算是补了一个trick，C不是什么好题

C. Swap Game(简单博弈)
题意：给定n个数。A，B两个人由A开始操作。
操作：轮流从第2到第n个位置选一个数然后令第一个数减一再和这个数交换。
当轮到某个人的时候发现此时第一个数是0那么这个人就输了

贪心的思路博弈，我A会每次让B去操作他现在看的从2到n最小的那个，B也一样，所以只要A不是最小值显然A就赢了。博弈退化为两人拼点的游戏。

#include 
using namespace std;
#define int long long
#define endl '\n'
const int N =1e5+100;
const int mod =998244353;
int a[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int minn=1e9+1;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            minn=min(minn,a[i]);
        }
        if(a[1]==minn)
        {
            cout<<"Bob"<<endl;
        }
        else
        {
            cout<<"Alice"<<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

D. Yet Another Problem(位运算trick，分类讨论)

题意：给定一个有n个数的数组，进行q次询问，每次询问给定一个区间，你可以在区间内做若干次操作，每次操作选择一个l，r值，在保证r-l+1是奇数的前提下，使得从l到r的所有元素被这段区间的异或和替换，每次询问输出最少的操作次数使得这次询问的区间全部变为0

思路：
默认顺序靠后的结论都不包括顺序靠前的不满足条件的情况

1.假如整个区间的异或和不为0，那么这个区间显然无法满足要求，直接输出-1.因为对一个数来讲，如果一次异或不能让这个数变成0，那么在异或又变回去了，没有任何意义。

2.如果是奇数区间，直接输出1

3.如果是偶数区间，如果前后端点为0，也直接输出1

4.如果是偶数区间，但是前后端点不为0，那么就可以看看异或的前缀是否为0，如果是，那么可以输出2

5.其他情况均为-1

重点是4这个操作，我们可以用map在坐标奇偶分开的前提下按照异或和来存储下标。

假设现在给定的区间是一个L，R，并且这段区间长度是偶数，那么我们所希望找的前缀异或和实际上就是从X[r]^X[L-1]=0，所以只要找到一个能和L-1构成奇数长度r，并且他们的异或和相等即可。这里只用二分去查找，如果L-1是个奇数，那么就在偶数的map里找。

#include 

using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5+100;

int xr[N],sum[N],pre[N],suf[N],a[N];

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    map<int,vector<int>> mp1,mp2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        xr[i]=xr[i-1]^a[i];
        sum[i]=sum[i-1]+a[i];
        if(i&1)
            mp1[xr[i]].push_back(i);
        else
            mp2[xr[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        int len=r-l+1;
        if(l==r&&a[l]!=0)
        {
            cout<<-1<<endl;
            continue;
        }
        if((xr[r]^xr[l-1])!=0)
        {
            cout<<-1<<endl;
            continue;
        }
        if(sum[l-1]==sum[r])
        {
            cout<<0<<endl;
            continue;
        }
        if(len%2)
        {
            cout<<1<<endl;
            continue;
        }
        if(a[l]==0||a[r]==0)
        {
            cout<<1<<endl;
            continue;
        }
        if(!((l-1)&1))
        {
            auto it=lower_bound(mp1[xr[l-1]].begin(),mp1[xr[l-1]].end(),l-1);
            if(it!=mp1[xr[l-1]].end()&&*it<=r)
            {
                cout<<2<<endl;
                continue;
            }
        }
        else
        {
            auto it=lower_bound(mp2[xr[l-1]].begin(),mp2[xr[l-1]].end(),l-1);
            if(it!=mp2[xr[l-1]].end()&&*it<=r)
            {
                cout<<2<<endl;
                continue;
            }
        }
        cout<<-1<<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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

ICPC澳门

D.Artifacts

这里题意自己读吧，思路也没什么思路，只是字符串的这种模拟我们有个操作还是要学一下

题目中出现大量的字符串切割，字符串转int，double等情况。

那么切割的话我们建议直接用string的find()去寻找位置，转int和double建议用string流来完成

比如我们想把string s="123456"变成int类型，就可以这样做

#include 
.......

signed main()
{
   string s="123456";
   int a;
   stringstream ss(s);
   ss>>a;
   cout<<a<<endl;
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

#include 

using namespace std;
#define double long double
const int N = 1e5+100;
char s[N];
map<string,double> mp;
signed main()
{
    string s;
    int t=25;
    while(t--)
    {
        getline(cin,s);
        if(s.empty())
            break;
        string temp=s.substr(s.find('+')+1);
        bool falg=false;
        if(temp[temp.length()-1]=='%')
        {
            temp=temp.substr(0,temp.length()-1);
            falg=true;
        }
        stringstream ss(temp);
        double num;
        ss>>num;
        if(falg)
            num*=0.01;
        mp[s.substr(0,s.find('+'))]+=num;
    }
    mp["ATK"]=1500.0*(1.0+mp["ATK Rate"])+mp["ATK"];
    mp["Crit Rate"]+=0.05;
    mp["Crit DMG Rate"]+=0.5;
    if(mp["Crit Rate"]>1)
        mp["Crit Rate"]=1;
    cout<<fixed<<setprecision(10)<<mp["ATK"]*(1.0-mp["Crit Rate"])+mp["ATK"]*(1.0+(mp["Crit DMG Rate"]))*mp["Crit Rate"];
    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

G - Game on Sequence

题意：现在有一个含有n个数的数组，每个数的取值范围是0到255，现在A，B两人在这个数组上博弈，他们从位置k开始，每次选择后面一个数满足与当前位置的数仅有一个二进制位不同后跳到这个数上。
当轮到某个人但是这个人不能往后条这个人就输了。

现在给定m次操作，第一个数字代表操作种类，1就是在数组后面再加一个数，2就是问从位置k开始，A，B轮流玩谁一定赢。

思路：

我们从一个数就考虑他如果行动。

加入现在对于数3来说，后面有若干个3，那么是谁赢呢？显然3和3之间可以跳，A可以一下子从当前的3跳到最后一个3上，但是发现这样的话，如果最后一个3后面有2或者是有1，B就会跳到2或者1上去，然后A就有可能输了，所以A可以一下子跳到最后一个他能跳到的数上。

那么在想想这样有可能A输吗？如果A输，那么肯定是从x跳到最后一个能去的数y上了，结果发现后面还有y能去而x不能去的数，但是可以验证这样的情况是不可能的。

所以当位置k的数是x但却不是最后一个出现的x时，A必赢。

那么如果是最后一个出现的x呢？

显然后面如果还有能跳的，A赢了，否则B赢了，就这么简单。

#include 
using namespace std;
int n,m,op,k;
const int MAXN = 4e5+10;
int arr[MAXN];
int occ[300];
int f[300];
bool cmp(int x,int y)
{
	return occ[x] > occ[y];//更靠右的数字优先处理
}
void ope()
{
	vector<int>vec;
	memset(f,1,sizeof(f));
	f[arr[n]]=0;
	for(int i=0;i<=255;i++)
	{
		if(occ[i])
            vec.push_back(i);
	}
	sort(vec.begin(),vec.end(),cmp);
	for(auto it:vec)
	{
		bool vis=0;
		for(int i=0;i<=7;i++)
		{
			int num=it^(1<<i);
			if(!f[num])//后面没能跳的了，没活了，要个打火机吧
			{
				vis=1;
				break;
			}
		}
		f[it]=vis;
	}
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m ;
	for(int i = 1;i <= n;i ++)
	{
		cin >> arr[i];
		occ[arr[i]] = i;
	}
	ope();
    while(m--)
    {
        cin>>op>>k;
        if(op==1)
        {
            n++;
            arr[n]=k;
            occ[k]=n;
            ope(); //更新状态
        }
        if(op==2)
        {
            int num=arr[k];
            if(occ[num]==k)
            {
                if(f[num])
                    cout<<"Grammy"<<endl;
                else
                    cout<<"Alice"<<endl;
            }
            else
                cout<<"Grammy"<<endl;
        }
    }
}
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

F. Fixing Networks

题意：给了n个点，让你构造出c个无向图，每个点的度数都为d。

能构造输出yes和方案，不能构造输出no。

思路：首先，构造题的切入点都是特殊情况，性质，相关定理等方向。

这个题来讲，可能比较复杂，我们想到能够满足条件的无向图最少也需要d+1个点，所以c*(d+1)>n是no，又发现边的数量应该是n*d/2，所以如果n和d相乘为奇数，也是no

接着发现零图和两点图是两种比较特殊的情况。

接着就是一般情况了。
按照刚才的分析，我们先用尽可能少的点去满足前c-1个无向图，那么也就是用（c-1）*(d+1)个点，这图显然构造出完全图即可。

剩下的点构成一个图，将剩下的点排列成一个环，对于每个点来说，我们让他左右链接，如果n是奇数，左边和右边都连接n/2后再连接距离他最远的那个点，就是正对面的那个点。如果是偶数就简单了，左右都连接n/2即可。

#include 

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

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n,d,c;
    cin>>n>>d>>c;
    if(!d)
    {
        if(n==c)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
        return 0;

    }
    if(d==1)
    {
        if(c*2==n)
        {
            cout<<"Yes"<<endl;
            for(int i=1;i<=n;i+=2)
            {
                cout<<i+1<<endl;
                cout<<i<<endl;
            }
        }
        else
        {
            cout<<"No"<<endl;
        }
        return 0;
    }
    if((c*(d+1)>n)||((n&1)&&(d&1)))
    {
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
	int res=n-(c-1)*(d+1);
	for(int i=1;i<=res;i++)
    {
		int k=d/2;
		vector<int> ans;
		for(int j=i-k;j<=i+k;j++)
        {
			if(i==j)
			 continue;
			if(j<=0)
			  ans.push_back(j+res);
			else if(j>res)
			  ans.push_back(j%res);
			else
			  ans.push_back(j);
		}
		if(d&1)
		    ans.push_back((i+res/2)%res+((i+res/2)%res==0?res:0));
		sort(ans.begin(),ans.end());
		for(auto x:ans)
		   cout<<x<<" ";
		cout<<endl;
	}
	for(int i=res+1;i<=n;i+=(d+1))
    {
		for(int j=i;j<=i+d;j++)
		{
			for(int k=i;k<=i+d;k++)
            {
				if(j==k)
				 continue;
				cout<<k<<" ";
			}
			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
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
82
83
84
85
86