A.黑白配
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int t,n;
cin>>t>>n;
int a[n+1];
while(t--){
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==0){
cnt1++;
}else{
cnt2++;
}
}
cout<<abs(cnt1-cnt2)<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
B.映射
思路：
数组a中的数只能对应一个b中的值，若对应了两个以上b中的值则No
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
int a[n+1];
int b[n+1];
int c[n+1];
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
if(c[a[i]]!=0&&c[a[i]]!=b[i]){
cout<<"No"<<endl;
return ;
}
c[a[i]]=b[i];
}
cout<<"Yes"<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
C.马走日
思路：
画图可知，n小于3或者m小于3时特判，n和m都等于3时为8，当n>=3并且m>=3时所有点都可到达
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
ll n,m;
cin>>n>>m;
ll ans;
if(n<3||m<3){
if(n==1||m==1){
ans=1;
}else if(n==2){
ans=1+(m-1)/2;
}else{
ans=1+(n-1)/2;
}
}else if(n==3&&m==3){
ans=8;
}else{
ans=n*m;
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
D.圆
思路：
题目求删除一些边的最小代价，可以反过来求选择一些边的最大价值，一些相交的边不能同时存在，那么就是区间dp的问题。
先将环拆分成链，链的长度为环的两倍，这样可以求点n-1、n-2……的区间；存储边，存储两次，例如x小于y时，存储x-y和y-（x+n），后者为y到第二圈的x的区间；根据题意，两条边不能交叉，一个端点只能有最多一条边;
开始区间dp，第一个for循环枚举终点i，第二个for循环枚举起点j，第三个for循环枚举起点所能到达的点v，若在区间范围内，这里的dp值为j-v的价值+区间（j+1）-（v-1）的值\(dp_{j+1,v-1}\)+区间（v+1）- i的值\(dp_{v+1,i}\)。
最后枚举起点1-n，范围为n，找到最大的区间值，就是最大价值，总数减最大价值就是最小代价。
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n,m;
cin>>n>>m;
ll sum=0;//所有边之和
vector<vector<pair<int ,int > > > edge(2*n+1);
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
if(x>y){
int t=x;
x=y;
y=t;
}
sum+=w;
edge[x].emplace_back(y,w);
edge[y].emplace_back(x+n,w);//y到第二圈的x
}
vector< vector<ll> > dp(2 * n + 1,vector<ll>(2 * n + 1, 0ll));//初始化二维数组
for(int i=1;i<=2*n;i++){//枚举区间终点
dp[i][i]=0;
for(int j=i-1;j>=1;j--){//枚举区间起点
if(i-j+1>n){
break;
}
dp[j][i]=dp[j+1][i];
for(int k=0;k<edge[j].size();k++){//枚举起点能到达的点
int v=edge[j][k].first;//边的到达点
int w=edge[j][k].second;//边的价值
ll cnt=w;
if(v>i){//超出区间范围
continue;
}
if(j+1<v-1){
cnt+=dp[j+1][v-1];
}
if(v+1<i){
cnt+=dp[v+1][i];
}
dp[j][i]=max(dp[j][i],cnt);
}
}
}
ll cnt=0;
for(int i=1;i<=n;i++){//枚举所有长为n的区间
cnt=max(cnt,dp[i][i+n-1]);
}
ll ans=sum-cnt;
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}