暴力模拟，先把他们弄成小写的，再把首字母弄成大写
t1
题意，将一段文章按英语格式输出ios
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
char a[199999];
int main(){
freopen("nigeru.in","r",stdin);
freopen("nigeru.out","w",stdout);
gets(a+1);int len=strlen(a+1);
for(int i=1;i<=len;i++){
if(a[i]!='.'&&a[i]!=' ')
if(a[i]<97&&a[i]>=65) a[i]+=32;
}
a[0]='.';
if(a[1]!='.'&&a[1]!=' ') a[1]-=32;
for(int i=1;i<=len;i++)
if(a[i-1]=='.'&&a[i]>=97&&a[i]<123)a[i]-=32;
else if(a[i-1]=='.'&&a[i]==' '){
int j=i;
while(a[j]==' ')j++;
if(a[j]>=97&&a[j]<123) a[j]-=32;
}
puts(a+1);
}
t2
每次数出两个相邻的，使字典序最大
每一次找最大的输出，sort一下就好了，再加个链表搞掉已经删除的web
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
int a[199999],n,nex[199999],h[199999],vis[199999];
struct st{
int s,t;
}p[199999];
bool cmp(const st&x,const st&y){
return x.s>y.s||x.s==y.s&&a[nex[x.t]]>a[nex[y.t]];
}
int main(){
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[i].s=a[i],p[i].t=i,nex[i]=i+1,h[i]=i-1;
sort(p+1,p+n,cmp);
vis[n+1]=1;
for(int i=1;i<=n;i++){
if(!vis[p[i].t]&&!vis[nex[p[i].t]]) {
printf("%d %d ",p[i].s,a[nex[p[i].t]]);
vis[p[i].t]=1;vis[nex[p[i].t]]=1;
nex[h[p[i].t]]=nex[nex[p[i].t]];
h[nex[nex[p[i].t]]]=h[p[i].t];
}
}
}
t3
题意: 看一个矩阵每行每列加一个0,1,2数最多可否变成几个三的倍数
暴力svg
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<ctime>
#define ll long long
using namespace std;
int n,m,a[1999][1999],sum[1999][1999],ans;
int check(int x){
int t[3];memset(t,0,sizeof t);
for(int i=1;i<=m;i++)
t[a[x][i]]++;
//printf("%d %d %d\n",t[0],t[1],t[2]);
if((t[0]>=t[1]&&t[0]>=t[2])||t[1]==t[2]) return 0;
return t[1]>t[2]?1:2;
}
int check2(int x){
int t[3];memset(t,0,sizeof t);
for(int i=1;i<=n;i++)
t[a[i][x]]++;
if((t[0]>=t[1]&&t[0]>=t[2])||t[1]==t[2]) return 0;
return t[1]>t[2]?1:2;
}
int dfs(int o){
int f=0;
/*for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%d ",a[i][j]);printf("\n"); } puts("\n");*/
for(int i=1;i<=n;i++){
int w=check(i);
//printf("%d\n",w);
//if(o==5) exit(0);
if(w!=0){
if(w==2)
{
for(int j=1;j<=m;j++) a[i][j]=(a[i][j]+1)%3;
f|=dfs(o+1);
for(int j=1;j<=m;j++) a[i][j]=(a[i][j]+2)%3;
}
if(w==1)
{
for(int j=1;j<=m;j++) a[i][j]=(a[i][j]-1+3)%3;
f|=dfs(o+1);
for(int j=1;j<=m;j++) a[i][j]=(a[i][j]+1)%3;
}
}
}
for(int i=1;i<=m;i++){
int w=check2(i);//printf("%d\n",w);
if(w!=0){
if(w==2)
{
for(int j=1;j<=n;j++) a[j][i]=(a[j][i]+1)%3;
f|=dfs(o+1);
for(int j=1;j<=n;j++) a[j][i]=(a[j][i]+2)%3;
}
if(w==1)
{
for(int j=1;j<=n;j++) a[j][i]=(a[j][i]-1+3)%3;
f|=dfs(o+1);
for(int j=1;j<=n;j++) a[j][i]=(a[j][i]+1)%3;
}
}
}
if(!f||o>n*m) {
int tot=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(a[i][j]%3==0) tot++;
ans=max(tot,ans);
return 0;
}
return f;
}
int main(){
freopen("haji1.in","r",stdin);
//freopen("haji.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),a[i][j]%=3;
dfs(0);
printf("%d",ans);
}
正解
只须要加 0，1，2
只须要枚举每一行
每一列就能够贪心了
o(n*m*3*3^n)
注意：只有3 6 9 12稳定，别的都不稳定，不是说3的倍数都稳定。。ui
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<ctime>
#define ll long long
using namespace std;
int n,m,a[19][19],ans;
void dfs(int x){
if(x>n){
int tot=0;
for(int i=1;i<=m;i++)
{
int t[3];
memset(t,0,sizeof t);
for(int k=0;k<3;k++)
for(int j=1;j<=n;j++)
{
if((a[j][i]+k)%3==0&&a[j][i]+k<=12) t[k]++;
}
tot+=max(t[0],max(t[1],t[2]));
}
ans=max(ans,tot);
return ;
}
for(int i=0;i<=2;i++)
{
for(int j=1;j<=m;j++) a[x][j]+=i;
dfs(x+1);
for(int j=1;j<=m;j++) a[x][j]-=i;
}
}
int main(){
freopen("haji.in","r",stdin);
freopen("haji.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
dfs(1);
printf("%d",ans);
}