背景
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\)事项：
- \(dp_{i,j,0}\)表示前\(i\)个连通块，
是否能塞入\(j\)个点到第一张桌子（白点） - \(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];//DP
void 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;
}