这周状态不太好，题目也比较毒瘤。。。
本来以为能400++，因为我打了四题的标算（T4模拟也算）+2题骗分
然而现实十分残酷，T3玄学（单项边，双向边。。。），T4玄学（模拟也能错我也很绝望）
T1:
本来听说是水题。。。然后就想多了想到状压去了。。。
发现每行翻转两次其实是一样的效果，于是只需翻转一次即可
大概就是说先2^n搜索出每一行是否需要翻转，然后再判断m列是否要翻转，更新答案
code:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[20][20];
int ans1=1e9,ans2=1e9;
char s[110];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++) a[i][j]=s[j]-'0';
}
for(int s=0;s<(1<<n);s++){
int c1=0;
for(int i=1;i<=n;i++)
if(s>>(i-1)&1){
for(int j=1;j<=m;j++)
a[i][j]^=1;
c1++;
}
int tot=0;
for(int j=1;j<=m;j++){
int c=0;
for(int i=1;i<=n;i++) c+=a[i][j];
if(n-c<c) c1++,tot+=n-c;
else tot+=c;
}
if(!tot) ans1=min(ans1,c1);
else ans2=min(ans2,tot);
for(int i=1;i<=n;i++)
if(s>>(i-1)&1) for(int j=1;j<=m;j++) a[i][j]^=1;
}
if(ans1==1e9) printf("%d",ans2);
else printf("%d",ans1);
return 0;
}T2:
贪心水题，sort一遍模拟计算答案
注意long long。。。。
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[1000010];
ll ans;
bool cmp(ll x,ll y){return x>y;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+n+1,cmp);
for(ll i=2;i<=n;i++)ans+=(ll)((i-1)*a[i]);
printf("%lld",ans);
return 0;
}T3:
被单双向边搞烦了、、干脆放弃希望。。。
发现其实是让我们求出1~n的一个全排列后计算答案
然后这里介绍一个STL：
next_permutation!!!
语法：next_permutation(c+1,c+n+1)，会生成一个大于当前c的全排列，如果没有就返回false
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
int a[110][110],b[110][110];
int bel[110],ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]++;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
b[x][y]++;
}
int tot=1;
for(int i=1;i<=n;i++)bel[i]=i;
while(next_permutation(bel+1,bel+n+1)){
if(tot) for(int i=1;i<=n;i++)bel[i]=i;
int cnt=0;tot=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cnt+=min(a[i][j],b[bel[i]][bel[j]]);
ans=max(ans,cnt);
}
printf("%d",ans);
return 0;
}T4:
这道题我直接上模拟了。。。根本不想打什么标算。。。
code:
#include<bits/stdc++.h>
using namespace std;
int a[6000010],n,m;
int cnt;
char ch,b[5000010];
int main(){
scanf("%d%d",&n,&m);
getchar();
for(int i=1;i<=n;i++){
ch=getchar();
a[i]=ch-'0';
}
scanf("%s",b+1);
for(int i=1;i<=m;i++){
int now=n;
if(b[i]=='+'){
a[now]++;
while(a[now]==2){
a[now]=0;
a[--now]++;
}
}
if(b[i]=='-'){
if(a[now]) a[now]=0;
else while(!a[now]){
a[now]=1;
now--;
}
a[now]=0;
}
if(b[i]=='*') n++,a[n]=0;
if(b[i]=='/') n--;
}
for(int i=1;i<=n;i++)putchar(a[i]+'0');
return 0;
}T5:
考虑每个点只有奇偶性重要，然后考虑每个点对答案奇偶性的贡献
发现除了对角线上的点，每个点都会被计算两边，也就是对奇偶性无影响。。。
于是只需要统计对角线的奇偶性即可
code:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans,x,y;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
scanf("%d",&x);
if(i==j&&x) ans^=1;
}
while(m--){
scanf("%d",&x);
if(x==1||x==2) scanf("%d",&y),ans^=1;
else printf("%d",ans);
}
return 0;
}T6:
这题有两个做法，dp太玄学根本不会，。。采用了雷霸霸的做法。。。
首先找规律，竖着刷当然是从头刷到尾最优
横着刷的话就是从最左边刷到最右边。。。
于是想到一个分治的做法，就是对于一段区间[l,r]，竖着刷最少次数肯定是r-l+1
那么横着刷就是这段区间的最小高度次数+除去下面一段的最小次数
这时候后者就可以分治递归下去了。。。
code:
#include<bits/stdc++.h>
using namespace std;
int ans,h[50010],n;
int solve(int l,int r,int last){
if(l==r) return 1;
int cnt=0,mn=1e9+1;
for(int i=l;i<=r;i++) mn=min(mn,h[i]);
for(int i=l;i<=r;i++){
if(h[i]==mn) continue;
int j;
for(j=i;j<=r;j)if(h[++j]==mn) break;
cnt+=solve(i,j-1,mn);
i=j-1;
}
return min(cnt+mn-last,r-l+1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&h[i]);
ans=solve(1,n,0);
printf("%d",ans);
return 0;
}
