Codeforces刷題第一周
最近一周都在codeforces上刷Div2的A，B，C，相比于其他OJ，codeforces上的更多是思維題，并不太注重考察資料結構和演算法，只要會基本語法和掌握STL就行，一般答案代碼量較少，用不到演算法模板，只要能夠找到題目的規律就行，
Codeforces Round #668(Div2) B
題目的意思是給定一個陣列，該陣列的和為0，陣列中若正數由右邊的負數消除不消費coin，若正數需要用左邊的負數消除，則需要消費coin，消費最少的coin實作陣列中每個元素是0，用模擬實作，
#include<stdio.h>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
int t,n;
long long int x;
vector<long long int> num;
scanf("%d",&t);
while(t--)
{
num.clear();
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lld",&x);
num.push_back(x);
}
long long int oppnum=0,negnum=0;//oppnum記錄留下的正數和，negnum記錄留下的負數和，這兩個值都會更新
for(int i=0;i<num.size();i++)
{
if(num[i]>=0) oppnum+=num[i];//如果為正數，統計到oppnum中
else//如果為負數，則可能會更新，消除正數
{
if(oppnum)//如果左邊有正數
{
if(oppnum>abs(num[i]))//如果左邊的正數和大于當前負數，則負數被消除為0,正數和oppnum會更新
{
oppnum=num[i]+oppnum;
num[i]=0;
}
else//如果左邊的正數和小于當前負數，則正數被消除為0,負數和negnum和當前數num[i]會更新
{
oppnum=0;
num[i]=num[i]+oppnum;
negnum=negnum+num[i];
}
}
else negnum=negnum+num[i];//如果左邊沒有正數，則更新negnum
}
}
printf("%lld\n",oppnum);
}
}
Codeforces Round #668(Div2) C
判斷一個未知字串（全部由’0’和’1’組成）能否滿足每一個k長度的子串中’0’和’1’的個數是一樣的，假設a[i]-a[i+k]滿足’0’和’1’的個數是相等的，若a[i+1]-a[i+1+k]要滿足這個條件，易得a[i+1+k]=a[i]，那這個字串是以k為周期的回圈字串，
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
string s;
int t,n,x,k;
scanf("%d",&t);
getchar();
while(t--)
{
scanf("%d%d",&n,&k);
getchar();
cin>>s;
bool judge=true;
int sum1=0,sum2=0;
for(int i=0;i<k;i++)
{
int tmp=-1;//tmp有兩個標記作用，一是標記這個回圈節中是否出現非''字符;二是若出現非'?'字符，標記是'0'還是'1'；
for(int j=i;j<n;j+=k)
{
if(s[j]!='?')//為'0'或者'1'
{
if(tmp!=-1&&s[j]-'0'!=tmp)//如果找到第一個非'?'字符并且不相等，則一定不回圈
{
judge=false;
break;
}
tmp=s[j]-'0';//此前沒找到非'?'字符或者與當前非'?'值相等
}
}
if(tmp!=-1)//若此回圈節已知（即至少出現一次非'?'值）
{
if(tmp==0) sum1++;
else sum2++;
}
}
if(sum1>k/2||sum2>k/2) judge=false;//若'1'或者'0'的數量超過一半，那一定不滿足條件
if(judge) printf("YES\n");
else printf("NO\n");
}
}
Codeforces Round #671(Div 2) A
有兩個人玩數字游戲，第一個人只能標記奇數位置上的未標記數字，第二個人只能標記偶數位置上的未標記數字，若最后一個剩下的是偶數，則第二個人贏；若最后一個剩下的是奇數，則第一個人贏，其實第一個人想贏，就必須把奇數留到最后（若有奇數），第二個同理，若游戲中陣列長度是1,則兩個人都不能標記，不用選就定勝負，若游戲中陣列長度是偶數，則第一個人把握主動權（實質上只能標記n-1個數字），只要陣列中有奇數，則能贏，否則不能贏；若為奇數，同理可推，
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
int t,n;
scanf("%d",&t);
string s;
while(t--)
{
int sum=0;
scanf("%d",&n);
getchar();
cin>>s;
if(s.length()==1)
{
int x=s[0]-'0';
if(x%2==0) printf("2\n");
else printf("1\n");
}
else if(s.length()%2==1)
{
for(int i=0;i<s.length();i=i+2)
{
int x=s[i]-'0';
if(x%2==1) sum++;
}
if(sum!=0) printf("1\n");
else printf("2\n");
}
else
{
for(int i=1;i<s.length();i=i+2)
{
int x=s[i]-'0';
if(x%2==0) sum++;
}
if(sum!=0) printf("2\n");
else printf("1\n");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/200130.html
標籤：python
上一篇：并查集（思路加簡單例題）