A. ABC String
題目大意：
實質上就是括號匹配，只不過‘A’，‘B’，'C’三個字母，每個字母都只能帶表一種括號，
思路：
在任何時刻右括號不能比左括號多，最后要剛好匹配即可，
AC Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
map<char,int>mapp;
mapp.clear();
string s;
cin>>s;
int len=s.length();
mapp[s[0]]=1;
mapp[s[len-1]]=-1;
if(s[0]==s[len-1])
cout<<"NO"<<endl;
else
{
int num0=0,num1=0,num2=0;
for(int i=0;i<len;i++)
{
if(mapp[s[i]]==1) num0++;
else if(mapp[s[i]]==-1) num1++;
else num2++;
}
if(num0==num1&&num2!=0) printf("NO\n");
else if(num0<num1&&num0+num2!=num1) printf("NO\n");
else if(num0>num1&&num0!=num1+num2) printf("NO\n");
else
{
num2=0;
if(num0<num1) num2=1;
else if(num0>num1) num2=-1;
int sum=0;
for(int i=0;i<len;i++)
{
if(mapp[s[i]]!=0) sum+=mapp[s[i]];
else sum+=num2;
if(sum<0) break;
}
if(sum<0) printf("NO\n");
else printf("YES\n");
}
}
}
//system("pause");
return 0;
}
B. Berland Crossword
題目大意：
有一個n*n大小的正方形，你可以給邊界的方塊涂色，然后給你上下左右邊界的黑色方塊的數量，問是否可行，
思路：
當每個邊界黑色方塊的數量<=n-2時當然是可行的，放在除了4個角上的位置即可，不然的話，其實我們也只要列舉4個角上的情況即可，
AC Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,a,b,c,d;
scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
if(a<=n-2&&b<=n-2&&c<=n-2&&d<=n-2) printf("YES\n");
else
{
int flag=0;
for(int i=0;i<=1;i++)
{
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
for(int f=0;f<=1;f++)
{
flag=0;
int a1=a,b1=b,c1=c,d1=d;
if(i==1) a1--,d1--;
if(j==1) a1--,b1--;
if(k==1) b1--,c1--;
if(f==1) c1--,d1--;
if(a1>=0&&a1<=n-2&&b1>=0&&b1<=n-2&&c1>=0&&c1<=n-2&&d1>=0&&d1<=n-2)
{
flag=1;
break;
}
}
if(flag==1) break;
}
if(flag==1) break;
}
if(flag==1) break;
}
if(flag==1) printf("YES\n");
else printf("NO\n");
}
}
//system("pause");
return 0;
}
C. 1D Sokoban
題目大意：
給你n個箱子的位置，和m個特殊位置，最開始時位于0點，推箱子時只能向左或向右推，不能把箱子回拉或者越過箱子，問最多有多少箱子在特殊位置上，
思路：
原點左邊的箱子只能往左推，源點右邊的箱子只能往右推，所以很明顯可以把大于0和小于0的箱子分成兩個部分來做，那么貪心的想，我們肯定是要把一些箱子一直推，直到某個特殊位置上，然后剩下的箱子不變，這樣的話我們遍歷每個特殊位置即可，把特殊位置idx[i]之前的箱子推到idx[i]這個位置上為止，然后idx[i]之后的箱子位置不變,這個時候我們還需要知道推到這個特殊位置之后，這一段連續的箱子有幾個是位于特殊位置上，看到這個資料范圍，很容易想到用樹狀陣列解決這個問題，
AC Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N],c[N],d[N];
int num[N];
int n,m;
unordered_map<int,int>mapp;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y)
{
for(int i=x;i<=1e9;i+=lowbit(i))
mapp[i]+=y;
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=mapp[i];
return ans;
}
unordered_map<int,int>mp;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int num1=0,num2=0,num3=0,num4=0;
mapp.clear(),mp.clear();
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x<0) a[++num1]=-1*x;
else b[++num2]=x;
}
sort(a+1,a+1+num1);
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
if(x<0) c[++num3]=-1*x;
else d[++num4]=x;
}
sort(c+1,c+1+num3);
for(int i=1;i<=num2;i++)
mp[b[i]]=1;
for(int i=1;i<=num4+1;i++) num[i]=0;
for(int i=num4;i>=1;i--)
if(mp[d[i]]) num[i]=num[i+1]+1;
else num[i]=num[i+1];
int sum=0;
int maxn=0;
int idx=1;
for(int i=1;i<=num4;i++)
{
update(d[i],1);
while(b[idx]<=d[i]&&idx<=num2) idx++;
maxn=max(maxn,num[i+1]+getsum(d[i])-getsum(d[i]-idx+1));
}
sum=sum+maxn;
mp.clear(),mapp.clear();
for(int i=1;i<=num1;i++)
mp[a[i]]=1;
for(int i=1;i<=num3+1;i++) num[i]=0;
for(int i=num3;i>=1;i--)
if(mp[c[i]]) num[i]=num[i+1]+1;
else num[i]=num[i+1];
maxn=0;
idx=1;
for(int i=1;i<=num3;i++)
{
update(c[i],1);
while(a[idx]<=c[i]&&idx<=num1) idx++;
maxn=max(maxn,num[i+1]+getsum(c[i])-getsum(c[i]-idx+1));
}
sum+=maxn;
printf("%d\n",sum);
}
//system("pause");
return 0;
}
D待補，，，，，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/265963.html
標籤：其他