A:http://codeforces.com/contest/1459/problem/A
题意:
有n张牌,每张上面有两个数字,排列这些牌之后比较上面n个数字的大小放在一起和下面n个数字放在一起的大小,如果上面大的数量多,RED获胜,如果相同则EQUAL 否则BLUE获胜
解析:
明确一点,不管怎么排,一张卡片的上下是不会变的。那么对于全排列,那么每一张都有机会放在第一个位置,那么直接看每张卡片上面比下面大的多还是下面比上面大的多即可。
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdio>
#include<cmath>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
const int inf=99999999;
char a[maxn],b[maxn];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string a,b;
cin>>a>>b;
int s1=0,s2=0;
for(int i=0;i<n;i++)
{
if(a[i]>b[i])
s1++;
else if(a[i]<b[i])
s2++;
}
if(s1==s2)
cout<<"EQUAL"<<endl;
else if(s1>s2)
cout<<"RED"<<endl;
else
cout<<"BLUE"<<endl;
}
}
B:http://codeforces.com/contest/1459/problem/B
题意:
机器人从原点开始走,第一步可以四面八方任意一个方向,下一次的走向就是上一次的走向的垂直方向。
求n步可能到达的所有位置数。
解析:
一看就知道是规律题了,dfs跑前几个。发现
1 4
2 4
3 12
4 9
5 24
6 16
7 40
8 25
发现,奇数位与上一个奇数位有关,每次差值+4,基础差值从n=4开始为12
偶数位与上一个偶数位有关,每次差值+2,基础差值从n=4开始为5
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdio>
#include<cmath>
#include<string.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int maxn=1e3+10;
const int inf=99999999;
int num[maxn];
int main()
{
num[1]=4;
num[2]=4;
num[3]=12;
int cnt1=5,cnt2=12;
for(int i=4;i<=1000;i++)
{
if(i%2)
{
num[i]=num[i-2]+cnt2;
cnt2+=4;
}
else
{
num[i]=num[i-2]+cnt1;
cnt1+=2;
}
}
int n;
cin>>n;
cout<<num[n]<<endl;
}
C:http://codeforces.com/contest/1459/problem/C
解析:
gcd(a,b)=gcd(a,b-a)
gcd(a,b)=gcd(a-b,b)
gcd(a,b,c....z)=gcd(a,gcd(b,c,....z))
那么:gcd(a1+b1,a2+b1,a3+b1......an+b1)
从a2开始,每一项减前一项有:
gcd(a1+bi , a2-a1,a3-a2......an-an-1)
那么预处理出gcd(a2-a1....an-an-1)==sum,然后跑b[]直接gcd(a1+bi,sum)即可。
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdio>
#include<cmath>
#include<string.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int maxn=2e5+10;
const int inf=99999999;
ll n,m;
ll a[maxn],b[maxn];
bool cmp(ll a,ll b)
{
return a>b;
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>b[i];
sort(a+1,a+1+n,cmp);
ll sum =a[2]-a[3];
for(int i=3;i<n;i++)
{
sum=gcd(sum,a[i]-a[i+1]);
}
for(int i=1;i<=m;i++)
{
ll md = gcd(a[1]+b[i],sum);
cout<<md<<" ";
}
cout<<endl;
}