A. Casimir’s String Solitaire
给定一个只存在ABC的字符串,一次操作可以同时删除任意位置的‘A’和‘B’或‘B’和‘C’,问能否删完。
只需判断B的数量是否等于A+C的数量。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn 50
int main() {
int T;
read(T);
while(T--) {
string a;
cin>>a;
int b[4]={0};
for(int i=0;i<a.size();i++) {
if(a[i]=='A') b[1]++;
else if (a[i]=='B') b[2]++;
else b[3]++;
}
if(b[2]==b[1]+b[3]) printf("YES\n");
else printf("NO\n");
}
return 0;
}
B. Shifting Sort
给定一个长度为n的数列,一次操作可以选择一个子串,将子串进行任意长度的滚动。
要求输出一个方案,在n次操作内使该数列递增。
由于不需要找出最小操作数,所以只需要每次操作把当前最小的数移动到合理的位置即可。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn 50
struct ans{
int l,r,d;
ans(){}
ans(int ll,int rr,int dd) {
l=ll,r=rr,d=dd;
}
};
int a[maxn+5],b[maxn+5],c[maxn+5];
vector<ans> s;
int main() {
int T;
read(T);
while(T--) {
int n;
read(n);
for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
s.clear();
for(int i=1;i<n;i++) {
int t;
if(a[i]==b[i]) continue;
for(int j=i;j<=n;j++) {
if(a[j]==b[i]) {
t=j;break;
}
}
memset(c,0,sizeof(c));
memcpy(c+1,a+1,(i-1)*sizeof(int));
memcpy(c+i,a+t,(n-t+1)*sizeof(int));
memcpy(c+i+n-t+1,a+i,(t-i)*sizeof(int));
memcpy(a+1,c+1,n*sizeof(int));
s.push_back(ans(i,n,t-i));
}
printf("%d\n",s.size());
for(int i=0;i<s.size();i++) {
printf("%d %d %d\n",s[i].l,s[i].r,s[i].d);
}
}
return 0;
}
C. Ticks
给一个只有黑白n*m的棋盘,问能不能完全由大于k的勾组成。
遍历枚举勾勾的最下端,暴力统计。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn 20
#define readc(a) do{scanf("%c",&a);}while(a!='.'&&a!='*')
int n,m,K;
bool a[maxn+5][maxn+5],b[maxn+5][maxn+5];
int main() {
int T;
read(T);
while(T--) {
read(n),read(m),read(K);
memset(a,0,sizeof(a));
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
char t;
readc(t);
if(t=='.') a[i][j]=0;
else a[i][j]=1;
}
memcpy(b,a,sizeof(a));
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
int k=0;
for( ; ; ) {
if(!a[i-k][j-k]||!a[i-k][j+k]) break;
k++;
}
if(k>K) {
while(k--) b[i-k][j-k]=b[i-k][j+k]=0;
}
}
}
bool ans=1;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(b[i][j]) {
ans=0;
break;
}
}
}
if(ans) printf("YES\n");
else printf("NO\n");
}
return 0;
}
D. Productive Meeting
有n个数,一次操作可以让任意两个数大于0的数-1,问最后无法操作时剩下数的最小值。
每次选出当前最大的两个数进行操作,可以用优先队列(大根堆)维护。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn (int)2e5
struct Pair {
int x,y;
Pair() {}
Pair(int xx,int yy) {
x=xx,y=yy;
}
};
struct ele {
int x,pos;
ele() {}
ele(int xx,int pp) {
x=xx,pos=pp;
}
bool operator < (const ele& e) const {
return x<e.x;
}
};
int n;
priority_queue<ele> a;
vector<Pair> b;
int main() {
int T;
read(T);
while(T--) {
b.clear();
while(a.size()) a.pop();
read(n);
for(int i=1; i<=n; i++) {
int x;read(x);
if(x!=0) a.push(ele(x,i));
}
while(a.size()>1) {
ele x1=a.top();a.pop();
ele x2=a.top();a.pop();
b.push_back(Pair(x1.pos,x2.pos));
x1.x--,x2.x--;
if(x1.x!=0) a.push(x1);
if(x2.x!=0) a.push(x2);
}
printf("%d\n",b.size());
for(int i=0;i<b.size();i++) {
printf("%d %d\n",b[i].x,b[i].y);
}
}
return 0;
}
E1. Permutation Minimization by Deque
给一个数列,需要按顺序把数列中的数插入双端队列中(可以是头部和尾部),使最后队列中的数字典序最小。
贪心,比当前头大的往尾部插,小或等于的往队首插。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn (int)2e5
int a[maxn+5];
deque<int> q;
int main() {
int T;
read(T);
while(T--) {
int n;
read(n);
for(int i=1;i<=n;i++) read(a[i]);
q.clear();
for(int i=1;i<=n;i++) {
if(a[i]<q.front()) q.push_front(a[i]);
else q.push_back(a[i]);
}
for(int i=1;i<=n;i++) {
printf("%d ",q.front());
q.pop_front();
}
printf("\n");
}
return 0;
}
E2. Array Optimization by Deque
给一个数列,需要按顺序把数列中的数插入双端队列中(可以是头部和尾部),使最后队列中的逆序对最少。
贪心,插入一个数的时候分别查询插在头部和尾部新增的逆序对数,选新增少的地方插。
查询操作用树状数组维护。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn (int)4e5
#define ll long long
struct Pair{
int x,num;
Pair() {}
Pair(int xx,int nn) {
x=xx,num=nn;
}
bool operator < (const Pair& e) const {
return x<e.x;
}
};
int n;
Pair a[maxn+5];
int b[maxn+5],c[maxn+5];
int lowbit(int x) {
return x&-x;
}
void add(int x) {
while(x<=n) {
c[x]++;
x+=lowbit(x);
}
}
int query(int x) {
int ans=0;
while(x>0) {
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int main() {
int T;
read(T);
while(T--) {
read(n);
for(int i=1;i<=n;i++) read(a[i].x),a[i].num=i;
sort(a+1,a+1+n);
int cnt=0;
a[0].x=(1e9)+1,memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) {
if(a[i].x!=a[i-1].x) ++cnt;
b[a[i].num]=cnt;
}
ll ans=0;
for(int i=1;i<=n;i++) {
int s=query(b[i]-1),r=i-1-query(b[i]);
if(r>s) ans+=s;
else ans+=r;
add(b[i]);
}
printf("%lld\n",ans);
}
return 0;
}
F. Array Stabilization (AND version)
给一个01数列,常数d,一次操作可以将数列滚动d个单位,并与原数列进行与操作。
问滚动多少次可以将数列变为全0。
一次操作即把每个位和后面d位(滚动意义上)与一遍,所以把每位和后d位建边,跑最短路,退出条件是走到一个为0的点。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn (int)1e6
#define ll long long
struct Pair{
int x,y;
Pair() {}
Pair(int xx,int yy) {
x=xx,y=yy;
}
bool operator < (const Pair& e) const {
return x<e.x;
}
};
int n,d;
bool a[maxn+5],use[maxn+5];
int cnt;
queue<Pair> que;
int spfa() {
int ans=0;
while(!que.empty()) {
int x=que.front().x,y=que.front().y;
que.pop();
int z=(x+d)%n;
if(use[z]) continue;
use[z]=1,++cnt;
que.push(Pair(z,y+1));
ans=max(ans,y+1);
}
if(cnt<n) return -1;
else return ans;
}
int main() {
int T;
read(T);
while(T--) {
memset(use,0,sizeof(use));
cnt=0;
read(n),read(d);
for(int i=0;i<n;i++) {
read(a[i]);
if(!a[i]) que.push(Pair(i,0)),use[i]=1,++cnt;
}
int ans=spfa();
printf("%d\n",ans);
}
return 0;
}
G. Minimal Coverage
有n根长度为a[n]的棍,现需将他们排成一根直线,使每根棍的两端分别与前一根和后一根的端点重合,求这样铺的最小长度。
看了题解。
dp[i][j]表示第i根棍,铺完后末端离最左端为j时,铺过的长度。
这里始终保持最左边为0,所以左端超过0时需要整体右移。
#include<bits/stdc++.h>
using namespace std;
#define read(a) scanf("%d",&a)
#define maxn (int)1e4
#define maxm (int)2e3
#define ll long long
struct Pair{
int x,y;
Pair() {}
Pair(int xx,int yy) {
x=xx,y=yy;
}
bool operator < (const Pair& e) const {
return x<e.x;
}
};
int n;
int a[maxn+5];
int dp[maxn+5][maxm*2+5];
int main() {
int T;
read(T);
while(T--) {
read(n);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=0;i<=n;i++) for(int j=0;j<=maxm*2;j++) dp[i][j]=(int)1e9;
dp[0][0]=0;
for(int i=1;i<=n;i++) {
for(int j=0;j<=maxm*2;j++) {
if(j+a[i]<=maxm*2) {
int x=max(dp[i-1][j],j+a[i]);
dp[i][j+a[i]]=min(dp[i][j+a[i]],x);
}
if(j-a[i]>=0) {
dp[i][j-a[i]]=min(dp[i][j-a[i]],dp[i-1][j]);
} else {
dp[i][0]=min(dp[i][0],dp[i-1][j]+a[i]-j);
}
}
}
int ans=(int)1e9;
for(int i=0;i<=maxm*2;i++) ans=min(ans,dp[n][i]);
printf("%d\n",ans);
}
return 0;
}