第七次codeforces竞技结束 #258 Div 2_sample test(s) input 2 1 3 4 5 output 4 1 2 2 1

这次出了两题，A和B，C的话我居然就差一个(n%3)就能ac了Q^Q 哭……

要是C加了那一行出了的话多帅气呀……

A. Game With Sticks

After winning gold and silver in IOI 2014, Akshat and Malvika want to have some fun. Now they are playing a game on a grid made of n horizontal and m vertical sticks.

An intersection point is any point on the grid which is formed by the intersection of one horizontal stick and one vertical stick.

In the grid shown below, n = 3 and m = 3. There are n + m = 6 sticks in total (horizontal sticks are shown in red and vertical sticks are shown in green). There are n·m = 9 intersection points, numbered from 1 to 9.

The rules of the game are very simple. The players move in turns. Akshat won gold, so he makes the first move. During his/her move, a player must choose any remaining intersection point and remove from the grid all sticks which pass through this point. A player will lose the game if he/she cannot make a move (i.e. there are no intersection points remaining on the grid at his/her move).

Assume that both players play optimally. Who will win the game?

2 2

Malvika

2 3

Malvika

3 3

Akshat

Note

Explanation of the first sample:

The grid has four intersection points, numbered from 1 to 4.

If Akshat chooses intersection point 1, then he will remove two sticks (1 - 2 and 1 - 3). The resulting grid will look like this.

Now there is only one remaining intersection point (i.e. 4). Malvika must choose it and remove both remaining sticks. After her move the grid will be empty.

In the empty grid, Akshat cannot make any move, hence he will lose.

Since all 4 intersection points of the grid are equivalent, Akshat will lose no matter which one he picks.

这道题呢意思是有这么多棒子摆成网格状，一人一次选一个交叉点拿走那俩棒子，没有交叉点可以拿的输。

因为一个交叉点由一纵一横组成，每次消除一纵一横，所以自然是纵横中某一个拿完了就结束了：

Code：

#include <queue>
#include <cmath> 
#include <memory> 
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
 
int cmp(const void *a, const void *b)
{
	return(*(int *)a-*(int *)b);
}
 
int main()
{
	int n,m;
	cin>>n>>m;
	cout<< (min(n,m)%2==0?"Malvika":"Akshat");
	return 0;
}

B. Sort the Array

3
3 2 1

yes
1 3

4
2 1 3 4

yes
1 2

4
3 1 2 4

no

2
1 2

yes
1 1

B题的话呢就是说有一个数组，我们只能选择其中一个连续的数组序列反序，问是否能一次操作后使整个数组升序。

用dp做标记找一段持续降序的序列反向，然后检测反向后的时不时严格升序即可：

Code：

#include <queue>
#include <cmath> 
#include <memory> 
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
 
int a[100001];
int dp[100001];
 
int cmp(const void *a, const void *b)
{
	return(*(int *)a-*(int *)b);
}
 
void arr_rev(int s,int e)
{
	int temp[100001];
	for(int i=s;i<=e;i++)
	{
		temp[i]=a[e+s-i];
	}
	for(int i=s;i<=e;i++)
	{
		a[i]=temp[i];
	}
}
 
int main()
{
	int n;	cin>>n;
	memset(a,0,sizeof a);
	memset(dp,0,sizeof dp);
	cin>>a[0];
	bool flag=true;
	int pos_start=0;
	for(int ni=1;ni<n;ni++)
	{
		cin>>a[ni];
		if(a[ni]>a[ni-1]) dp[ni]=dp[ni-1]+1;
		else 
		{
			dp[ni]=0;
			flag=false;
			if(pos_start==0)pos_start=ni;
		}
	}
	if(flag)
	{
		cout<<"yes"<<endl<<"1 1";
		return 0;
	}
	//for(int i=0;i<n;i++)cout<<dp[i]<<" ";
	int start=0,end=0;
	if(dp[1]==0)
	{
		end=1;
		int sup[100001];
		memset(sup,0,sizeof sup);
		while(dp[end]==0)
		{
			end++;
			if(end==n)break;
		}
		arr_rev(0,end-1);
	}
	else
	{
		start=pos_start-1;
		end=pos_start;
		while(dp[end]==0)
		{
			end++;
			if(end==n)break;
		}
		arr_rev(start,end-1);
	} 
	bool aflag=true;
	for(int i=1;i<n;i++)
	{
		//cout<<a[i]<<endl;
		if(a[i]<a[i-1])aflag=false;
	}
	puts(aflag?"yes":"no");
	if(aflag)cout<<start+1<<" "<<end<<endl;
	return 0;
}

C. Predict Outcome of the Game

5
3 0 0 0
3 3 0 0
6 4 1 0
6 3 3 0
3 3 3 2

yes
yes
yes
no
no

这道题的意思是有3个队伍，总共要打n场比赛，已经打了k场，这k场之后一队和二队的得分差的绝对值为d1，二队和三队得分差绝对值为d2，问有没有可能n场都打完了之后三个队伍平手。

经枚举题意，这道题呢有这么几个隐含条件：

1、n可以不是3的倍数 Test 4 n=999999980 ，这就是我wa的原因……我没有写(n%3==0)cout<<"no"<<endl;

2、Note中说明了不是循环打，可以就两个队打到天荒地老……

1-2 (win 2), 1-3 (win 3), 1-2 (win 1), 1-3 (win 1)，1-2 (win 2), 1-3 (win 3). 

3、存在 【k场之后不可能存在d1、d2的此种数据】 的可能性： Test 5 n=1,k=1,d1=0,d2=0

这道题如下判定即可：

1、n是否能被3整除（场数都不能被3整除的话最后三个人怎么可能win数相同）

2、d1=d2=0 的时候直接看n-k是否能被3整除

3、绝对值d1,d2 上符号，四种情况：++,+-,-+,--

依次判断1) 此种情况下最大的那个队伍当前胜场有没有超过n/3

2) 三个队按照当前情况下已打场数和是否超过k

3) 三个队按照最大队补齐之后k场剩余场是否为非负

Code：

#include <cmath> 
#include <memory> 
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 ll;
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
 
int cmp(const void *a, const void *b)
{
	return(*(int *)a-*(int *)b);
}
 
int main()
{
	int cases=0;
	scanf("%d",&cases);
	for(int _case=1;_case<=cases;_case++)
	{
		ll n,k,d1,d2,rest=0;
		cin>>n>>k>>d1>>d2;
		rest=n-k;
		if(n%3!=0)
		{
			cout<<"no"<<endl;
			continue;
		} 
		if(rest==0 && d1==0 && d2==0)
		{
			cout<<"yes"<<endl;
			continue;
		}
		if(d1==0 && d2==0)
		{
			cout<<(rest%3==0?"yes":"no")<<endl;
			continue;
		}
		if(rest<0)
		{
			cout<<"no"<<endl;
			continue;
		}
		
		ll rest1=rest-d1-d1-d2;		// >>
		if((d1+d2)>(n/3)) rest1=-1;
		if(d1+d2+d2>k) rest1=-1;
		ll rest2=rest-max(d1,d2)-(max(d1,d2)-min(d1,d2));// >< 
		if(max(d1,d2)>(n/3)) rest2=-1;
		if(d1+d2>k)rest2=-1;
		ll rest3=rest-d1-d2;		// <>
		if(max(d1,d2)>(n/3)) rest3=-1;
		if(max(d1,d2)+max(d1,d2)-min(d1,d2)>k) rest3=-1;
		ll rest4=rest-d1-d2-d2;		// <<
		if((d1+d2)>(n/3)) rest4=-1;
		if(d1+d1+d2>k) rest4=-1;
		
		if(rest1>=0 && rest1%3==0)cout<<"yes"<<endl;
		else if(rest2>=0 && rest2%3==0)cout<<"yes"<<endl;
		else if(rest3>=0 && rest3%3==0)cout<<"yes"<<endl;
		else if(rest4>=0 && rest4%3==0)cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
	return 0;
}
 

                                                                        D. Count Good Substrings

bb

1 2

baab

2 4

babb

2 5

babaa

2 7

这道题呢是说一个【仅由a、b组成】的字符串，其中任意一个子串压缩（压缩的意思是所有连续的a或连续的b都由一个a或b来代替）后为回文的话成为好子串，问偶数长度的偶子串有多少个，奇数长度的偶子串有多少个。

技巧：

1、压缩后获得的一定是a、b相间的字符串，如a\ab\aba\ababababababa\bababa

2、压缩后的长度若为奇数则为回文

3、原字符串的偶数位到偶数位、奇数位到奇数位的子串长度为奇数，奇数位到偶数位、偶数位到奇数位的子串长度为偶数

4、所以这是个数学题

Code：

#include <queue>
#include <cmath> 
#include <memory> 
#include <cctype>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
 
string s;
char str[maxn];
int len,f[2][2];
long long ans[2];
 
int main()
{
    while(scanf("%s",str)==1)
	{
        len=strlen(str);
        memset(f,0,sizeof f);
        memset(ans,0,sizeof ans);
        for(int i=0;i<len;i++)
		{
            f[str[i]-'a'][i%2]++;	 
            ans[0]+=f[str[i]-'a'][1-i%2];
            ans[1]+=f[str[i]-'a'][i%2];
        }
        cout<<ans[0]<<' '<<ans[1]<<endl;
    }
    return 0;
}