codeforces 1099E-Nice table
2024-10-07 22:54:48
传送门：QAQQAQ
题意：给你一个矩阵只有AGCT，若对于每一个2*2的子矩阵中的四个字母互不相同，则称为这个矩阵是nice的，问至少变矩阵中的几个点可以使矩阵变nice
思路：没什么思路……就是大模拟。
我们先糊出一个结论：对于一个nice矩阵，要么每一行是两个字母循环出现，要么是每一列两个字母循环出现。（所以对于一些无从下手的题可以先模拟几个数据找普遍规律）
所以我们可以枚举左上角的2*2矩阵，再分类是关于行重复还是关于列重复，再关于每一个重复的行或列分类是ABABAB还是BABABA，然后爆搜答案和ans比较，用tmp维护再分类时的矩阵，用tmp来更新ans矩阵
代码量过大，本人在写程序时遇到以下问题：
1.更新时best矩阵忘清零
2.string直接赋值，而没有push_noback
3.智障地把ans=now写成了now=ans
代码（长度要破纪录了）：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
int n,m;
string s[],best[];
vector<int> a[],tmp[];
int t[][],top=,ans=;
int fn(char c)
{
if(c=='A') return ;
else if(c=='C') return ;
else if(c=='G') return ;
else if(c=='T') return ;
}
char fc(int c)
{
if(c==) return 'A';
else if(c==) return 'C';
else if(c==) return 'G';
else if(c==) return 'T';
}
void print()
{
cout<<"That's OK!"<<endl;
}
int main()
{
//freopen("Nice.in","r",stdin);
//freopen("Nice.out","w",stdout);
ios::sync_with_stdio();
cin.tie();
cout.tie();
scanf("%d%d",&n,&m);
for (int i=;i<n;++i)
{
cin>>s[i];
for(int j=;j<m;j++) a[i].push_back(fn(s[i][j]));
}
for(int c1=;c1<=;c1++)
for(int c2=;c2<=;c2++)
for(int c3=;c3<=;c3++)
{
int c4=-c1-c2-c3;
if(c1==c2||c2==c3||c1==c3) continue;
t[++top][]=c1; t[top][]=c2;
t[top][]=c3; t[top][]=c4;
} for(int tt=;tt<=;tt++)
{
int c1=t[tt][],c2=t[tt][],c3=t[tt][],c4=t[tt][];
for(int b=;b<=;b++) //0:heng 1:shu
{
int now=;
if(!b)
{
for(int i=;i<n;i++) tmp[i].clear();
for(int i=;i<n;i++)
{
if(i%==)
{
if(i==)
{
for(int j=;j<m;j++) {
if(j%==)
{
if(c1!=a[i][j]) now++;
tmp[i].push_back(c1);
}
if(j%==)
{
if(c2!=a[i][j]) now++;
tmp[i].push_back(c2);
}
}
}
else
{
int tmp1=,tmp2=;
for(int j=;j<m;j++) {
if(j%==)
{
if(c1!=a[i][j]) tmp1++;
if(c2!=a[i][j]) tmp2++;
}
else
{
if(c1!=a[i][j]) tmp2++;
if(c2!=a[i][j]) tmp1++;
}
}
if(tmp1<=tmp2)
{
now+=tmp1;
for(int j=;j<m;j++)
if(j%==) tmp[i].push_back(c1);
else tmp[i].push_back(c2);
}
else
{
now+=tmp2;
for(int j=;j<m;j++)
if(j%==) tmp[i].push_back(c2);
else tmp[i].push_back(c1);
}
}
}
else
{
if(i==)
{
for(int j=;j<m;j++)
{
if(j%==)
{
if(c3!=a[i][j]) now++;
tmp[i].push_back(c3);
}
if(j%==)
{
if(c4!=a[i][j]) now++;
tmp[i].push_back(c4);
}
}
}
else
{
int tmp1=,tmp2=;
for(int j=;j<m;j++) {
if(j%==)
{
if(c3!=a[i][j]) tmp1++;
if(c4!=a[i][j]) tmp2++;
}
else
{
if(c3!=a[i][j]) tmp2++;
if(c4!=a[i][j]) tmp1++;
}
}
if(tmp1<=tmp2)
{
now+=tmp1;
for(int j=;j<m;j++)
if(j%==) tmp[i].push_back(c3);
else tmp[i].push_back(c4);
}
else
{
now+=tmp2;
for(int j=;j<m;j++)
if(j%==) tmp[i].push_back(c4);
else tmp[i].push_back(c3);
}
}
}
}
if(now<ans)
{
ans=now;
for(int i=;i<n;i++) best[i].clear();//!!!!!
for(int i=;i<n;i++)
for(int j=;j<m;j++) best[i].push_back(fc(tmp[i][j]));
//string不要直接赋值！！！
}
}
else
{
for(int j=;j<m;j++) tmp[j].clear();
for(int j=;j<m;j++)
{
if(j%==)
{
if(j==)
{
for(int i=;i<n;i++) {
if(i%==)
{
if(c1!=a[i][j]) now++;
tmp[j].push_back(c1);
}
if(i%==)
{
if(c3!=a[i][j]) now++;
tmp[j].push_back(c3);
}
}
}
else
{
int tmp1=,tmp2=;
for(int i=;i<n;i++) {
if(i%==)
{
if(c1!=a[i][j]) tmp1++;
if(c3!=a[i][j]) tmp2++;
}
else
{
if(c1!=a[i][j]) tmp2++;
if(c3!=a[i][j]) tmp1++;
}
}
if(tmp1<=tmp2)
{
now+=tmp1;
for(int i=;i<n;i++)
if(i%==) tmp[j].push_back(c1);
else tmp[j].push_back(c3);
}
else
{
now+=tmp2;
for(int i=;i<n;i++)
if(i%==) tmp[j].push_back(c3);
else tmp[j].push_back(c1);
}
}
}
else
{
if(j==)
{
for(int i=;i<n;i++) {
if(i%==)
{
if(c2!=a[i][j]) now++;
tmp[j].push_back(c2);
}
if(i%==)
{
if(c4!=a[i][j]) now++;
tmp[j].push_back(c4);
}
}
}
else
{
int tmp1=,tmp2=;
for(int i=;i<n;i++) {
if(i%==)
{
if(c2!=a[i][j]) tmp1++;
if(c4!=a[i][j]) tmp2++;
}
else
{
if(c2!=a[i][j]) tmp2++;
if(c4!=a[i][j]) tmp1++;
}
}
if(tmp1<=tmp2)
{
now+=tmp1;
for(int i=;i<n;i++)
if(i%==) tmp[j].push_back(c2);
else tmp[j].push_back(c4);
}
else
{
now+=tmp2;
for(int i=;i<n;i++)
if(i%==) tmp[j].push_back(c4);
else tmp[j].push_back(c2);
}
}
}
}
if(now<ans)
{
ans=now;//ans，now写反了。。。
for(int i=;i<n;i++) best[i].clear();//!!!!!
for(int i=;i<n;i++)
for(int j=;j<m;j++) best[i].push_back(fc(tmp[j][i]));
}
}
}
}
for(int i=;i<n;i++)
{
for(int j=;j<m;j++) printf("%c",best[i][j]);
puts("");
}
return ;
}
最新文章
- 每天一个linux命令（38）：cal 命令
- 免费素材：包含 250+ 组件的 DO UI Kit
- BestCoder Round #87 1003 LCIS[序列DP]
- yii2自动生成表单
- Ubuntu安装Osmocom-BB一只猿多频点WEB脚本
- unity c#
- IE10与IMG图片PNG显示不了 WP中的WebBrowser中无法查看PNG格式的图片
- MongoDB基础知识 01
- Android开发环境的搭建之（一）Java开发环境的安装
- android 基本控件使用
- android 点滴记录
- javascript实现禁止右键和F12查看源代码
- 【python学习笔记】5.条件、循环和其他语句
- elasticsearch6.6.2在Centos6.9的安装
- .zip压缩版MySql的安装（ ）
- IntelliJ IDEA安装、配置、测试
- VRRP虚IP漂移
- 106 miles to Chicago---zoj2797（最短路问题，求概率，模板）
- AC日记——[SCOI2009]游戏 bzoj 1025
- AVL重平衡细节——插入