补题报告3

背景

2024-10-3上午打的比赛（CSP-J模拟2），作赛后总结报告。

---

IP地址（\(ip\)）

赛时AC。

概述

每个设备有一个对应的\(IP\),先给出对应的设备与\(IP\),再给出几个\(IP\)，求对应的设备。

思路

\(map\) 存储，映射

我的代码

代码(点左边三角展开)

#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
int n,q;
map <string,string> mp;
int main() {
//	freopen("ip.in","r",stdin);
//	freopen("ip.out","w",stdout);scanf("%d",&n);for(int i=1; i<=n; ++i) {string a,b;cin >> a >> b;mp[b] = a;}scanf("%d",&q);for(int i=1; i<=q; ++i) {string b;cin >> b;cout << mp[b] << "\n";}
//	fclose(stdin);
//	fclose(stdout);return 0;
}

---

是否同构（\(same\)）

概述

同构数组：两个数组(\(a\),\(b\)) , 在\(b\)数组不变情况下，将\(a\)数组的前\(k\)项与后\(k\)项交换，能得到\(a=b\)
给出两数组，判断是否为同构数组

我的代码

Code(错)

#include <cstdio>
using namespace std;
const int maxn = 1e6+555;
int t;
int a[maxn];
int b[maxn];
int main() {
//	freopen("same.in","r",stdin);
//	freopen("same.out","w",stdout);scanf("%d",&t);while(t--) {int n;scanf("%d",&n);for(int i=1; i<=n; ++i) scanf("%d",&a[i]);for(int i=1; i<=n; ++i) scanf("%d",&b[i]);bool flag = 0;for(int i=1; i<=n; ++i) {if(a[i] != b[n-i+1] || a[n-i+1] != b[i])for(int j=i; j<=n-i+1; ++j)if(a[j] != b[j] || a[n-j+1] != b[n-j+1]) {flag = 1;break;}if(flag) break;}if(flag) printf("No\n");else printf("Yes\n");}
//	fclose(stdin);
//	fclose(stdout);return 0;
}

喜得10分

错因

题目描述 : \(swap(a_1,a_{N−k+1}),⋯,swap(a_k,a_N))\)
我的代码 : \(swap(a_1,a_N),⋯,swap(a_k,a_{N−k+1}))\)
QvQ

正解

• 开局判断，若完全一致，直接通过

• 不行，找\(a_i = b_1\)，并用\(pos\)记录\(i\)

• 再将\(pos\)前后交换,然后再判断是否一致

正解代码

Code(对)

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e6+1111;int t;
int a[maxn];
int b[maxn];
int n;
bool Check() {for(int i=1; i<=n; ++i)if(a[i] != b[i]) return 0;return 1;
}int main() {cin >> t;while(t--) {cin >> n;for(int i=1; i<=n; ++i) scanf("%d",&a[i]);for(int i=1; i<=n; ++i) scanf("%d",&b[i]);if(Check()) {//完全一致直接通过 printf("Yes\n");continue;}int pos;for(pos=n/2+1;pos<=n; ++pos) if(a[pos] == b[1]) break;//找到和b数组头一样的 for(int i=pos;i<=n;++i)//翻转a数组 swap(a[i],a[i-pos+1]);if(Check()) cout << "Yes\n";//二轮判断 else cout << "No\n";}return 0;
}

---

箱子(\(box\))

10分 (不嘻嘻

概述

给\(n\)个箱子重量，每次最多能合并\(m\)个
合并后的大箱子重量与花费的体力都为合并的箱子重量之和
求最后合并完，花费最少多少体力？

思路(我的)

每次都排序，合并掉最小的\(m\)个，直到剩一个。

爆 炸

代码

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn =1e5+111;
int cnt;//0的个数 
int n,m;
long long ans;
long long a[maxn];
signed main(){
//	freopen("box.in","r",stdin);
//	freopen("box.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%lld",&a[i]);while(cnt < n-1){sort(a+cnt+1,a+n+1);long long h=0;//合并的几个箱子的重量和for(int i=1;i<=m;++i){h+=a[cnt+i];a[cnt+i] = 0; } a[cnt+m] = h;ans += h;cnt += m-1;}printf("%lld",ans);
//	fclose(stdin);
//	fclose(stdout); return 0;
}

正解

使用优先队列(priority_queue)装一手

代码

Code(对）

#include <queue>
#include <iostream>
typedef long long ll;
using namespace std;ll sum;
int n,m; 
priority_queue<ll,vector<ll>,greater<ll> > q;
signed main(){cin >> n >> m;for(int i=1;i<=n;++i){int x;cin >> x;q.push(x); }if((n-1) % (m-1) > 0){//抛去第n个人，剩余的是不是(m-1)的倍数，最后+第n个人正好是m的倍数int cnt = (m-1) - (n-1) % (m-1);while(cnt--) q.push(0);//最后不足的要补0 }while(!q.empty()){ll h=0;bool flag=0;for(int i=1;i<=m;++i){if(!q.empty()){h += q.top();q.pop();}else{flag = 1;break;}}if(flag) break;q.push(h);sum += h;}return 0;
}

---

社恐的聚会(\(party\))

概述

有\(n\)个人，要参加聚会，但是很社恐，所以都想跟互相认识的人坐一张桌。
有两张桌 (寒酸)，问能否将这些人安排好？
如果行，人多的那张桌最少有几人？

思路

骗分，40 (喜

40分

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 514;
int n;
int k;
int cnt; 
bool g[maxn][maxn];
int main() {
//	freopen("party.in","r",stdin);
//	freopen("party.out","w",stdout); scanf("%d",&n);for(int i=1; i<=n; ++i) {for(int j=1; j<=n; ++j) {scanf("%d",&g[i][j]);}}if(n <= 2) printf("Yes\n1");else if(n == 3){bool flag = 0;if(g[1][2] == 1 && g[2][1] == 1) flag = 1;if(g[1][3] == 1 && g[3][1] == 1) flag = 1;if(g[2][3] == 1 && g[3][2] == 1) flag = 1;if(flag) printf("Yes\n2");else printf("No\n"); }else {for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(g[i][j] == 0) ++k;if(g[i][j] && g[j][i]) ++cnt;}}if(k == n*n || cnt <= 1) printf("No\n");else {int ans;if(n%2==1) ans = n/2+1;else ans = n/2;printf("Yes\n%d",ans);}}
//	fclose(stdin);
//	fclose(stdout);return 0;
}

正解

二分图+\(DFS\)+\(DP\), 无敌了
没啥好说的(其实是不会)
好吧，说两句：
将不是互相认识的人建边，对所有连通块进行判断当前连通块是否为二分图，不是直接结束(输出\(No\))，是，记录各连通块中黑白点数量，然后做超级无敌\(DP\)求解

注意，黑点和白点本质上没有区别，每个连通块都可以黑白互换

\(DP\)事项：

1. \(dp_{i,j,0}\)表示前\(i\)个连通块，
   是否能塞入\(j\)个点到第一张桌子（白点）
2. \(dp_{i,j,1}\)表示前\(i\)个连通块，
   是否能塞入\(j\)个点到第二张桌子（黑点）

超级无敌代码(这次真无敌了)

#include <iostream>
using namespace std;
const int maxn = 522;int n,g[maxn][maxn];
bool vis[maxn];
int color[maxn];//黑白
int m[maxn][2],h;//每个连通块黑白颜色数量
int head[maxn],next[maxn * maxn] ,to[maxn * maxn],cnt;
bool f[maxn][maxn][2];//DPvoid Insert(int u,int v) {next[++cnt] = head[u];head[u] = cnt;to[cnt] = v;
}bool dfs(int u,int c) { //u是当前点,c是颜色vis[u] = 1;color[u] = c;m[h][c]++;for(int i=head[u]; i; i=next[i]) { // 遍历int v = to[i];if(vis[v])if(color[u] == color[v]) return 0;else if(!dfs(v,c^1)) return 0;//0^1=1,1^1=0,c^1是取反}return 1;
}int main() {cin >> n;for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)cin >> g[i][j];for(int i=1; i<=n; ++i)for(int j=1; j<=n; ++j)//如果不是互相认识if(!(g[i][j] && g[j][i])) {Insert(i,j);Insert(j,i);}for(int i=1; i<=n; ++i) {if(vis[i]) continue;++h;//连通块数if(!dfs(i,0)) {cout << "No\n";return 0;w}}dp[0][0][0] = 1;dp[0][0][1] = 1;int maxx = n/2;for(int i=1; i<=maxx; ++i) {for(int j=m[i][0]; j<=maxx; ++j) {f[i][j][0] |= f[i-1][j-m[i][0]][0];f[i][j][0] |= f[i-1][j-m[i][0]][1];}for(int j=m[i][1]; j<=maxx; ++j) {f[i][j][1] |= f[i-1][j-m[i][1][0];f[i][j][1] |= f[i-1][j-m[i][1][1];}}int ans = 0;for(int i=maxx;i>=1;--i){//找一桌最多坐几个 if(f[h][i][0] || f[h][i][1]){ans = n - i;break;}}cout << "Yes\n";cout << ans; return 0;
}

官方题解