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;
}