2025东北CCPC（部分+详解）

一：年少的誓约II: 

 

// Problem: F - 年少的誓约Ⅱ
// Contest: Virtual Judge - sdccpc20250528
// URL: https://vjudge.net/contest/719805#problem/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
#define double long double
#define sqrt sqrtl
//const int mod = 998244353;void solve()
{int x0,y0,x1,y1,x2,y2;cin>>x0>>y0>>x1>>y1>>x2>>y2;double dm = y0*6.0;//先将初始位置的时分都转换成角度 方便以后的比较和计算double dh = x0*30.0+y0*0.5;//每小时转动的角度为30°，每分钟分针转动的角度为6°，时针转动的角度为0.5°；int t = x0*60+y0,l = x1*60+y1,r = x2*60+y2;if(t>=l&&t<=r){cout<<x0<<' '<<y0<<endl;//如果当前的时间正好就在约会范围内 就直接输出（因为最优解是不用动->转动角度为0）return ;}double mx = 1e18;int anx,any;for(int i=l;i<=r;i++){int h = i/60,m = i%60;//先把每一个时间转化为小时和分钟double hh = h*30.0+m*0.5;//计算当前的约会时间的时针所在位置的角度double mm = m*6.0;//计算当前的约会时间分针所在位置的角度double _m = fmin(360.0-fabs(mm-dm),fabs(mm-dm));//计算每个优弧和劣弧上的角度 取最小值double _h = fmin(360.0-fabs(hh-dh),fabs(hh-dh));//都与初始时刻的角度进行做差比较 取最小值double sum = _m + _h;if(sum<mx){mx = sum;anx = h;any = m;}}cout<<anx<<' '<<any<<endl;
}
/*坑：题目中说的是在转动指针时另一个指针不会发生变化 但是并不意味着这个钟表在分针移动时时针不会动 所以不管是起始时间还是终止时间时针的角度都会受到分针的转动所带来的影响（时针计算角度是需要加上分针转动导致时针转动的角度）意思就是说 ： 起始时间时针就有偏移 你需要将钟表转动到符合要求的位置（合法位置）这就需要在遍历时加上时针的偏移
*/
signed main()
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

// Problem: G - 加边
// Contest: Virtual Judge - sdccpc20250528
// URL: https://vjudge.net/contest/719805#problem/G
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se secondconst int N = 1e5+10;
vector<int> a(N,0),ans;void solve()
{int n,m,x,y,sum=0;cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;a[x]++; a[y]++;}for(int i=1;i<=n;i++){if(a[i]&1){sum++;ans.push_back(i);}}if(!(sum&1))cout<<sum/2;else cout<<sum/2+1;cout<<endl;if(!(sum&1))for(int i=0;i<ans.size();i+=2)cout<<ans[i]<<' '<<ans[i+1]<<endl;else{for(int i=0;i<ans.size()-1;i+=2)cout<<ans[i]<<' '<<ans[i+1]<<endl;cout<<ans[ans.size()-1]<<' '<<ans[ans.size()-1]<<endl;}
}signed main()
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
} 

 

这道题就是把情况想全面一点（注意题目没说S和T不能相等）

如果两个地方（起始位置和终点）是死对头的话就一定是NO因为题目要求路上不能同时出现两个互相为死对头的城市

又因为一个城市只能和另外的一个城市有仇 并且当前目的地和起始位置不是仇家

那么分两种情况

1-如果起始位置和仇家分别位于两侧的话 一定是yes 因为我可以直接从起始位置一步走到终点

2-如果位于同侧的话：

只有当n<=2的时候是no

其余情况 第二排中与起始位置有仇的城市一定和目的地没有仇 而起始城市一定与其他城市没有仇那么我们可以从起始城市走到另一排的其他城市 而其他城市如果n＞=3的时候就一定有一个城市与与起始城市有仇的城市没有仇 那么我们可以通过这个城市走到与目标城市没有仇的城市最后一步到达代码如下

// Problem: I - 王国------求策
// Contest: Virtual Judge - sdccpc20250528
// URL: https://vjudge.net/contest/719805#problem/I
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 5e5+10;
int a[N];void solve()
{int n,s,t;cin>>n>>s>>t;for(int i=1;i<=n;i++){cin>>a[i];a[a[i]]=i;}if(s==t){cout<<"Yes"<<endl;return ;}if(a[s]==t){cout<<"No"<<endl;return ;}if(s<=n&&t>n||s>n&&t<=n){cout<<"Yes"<<endl;return ;}if(n<=2){cout<<"No"<<endl;return ;}cout<<"Yes"<<endl;
}signed main()
{IOSint T=1;cin>>T;while(T--) solve(); return 0;
} 

 

// Problem: K - 微信小游戏
// Contest: Virtual Judge - sdccpc20250528
// URL: https://vjudge.net/contest/719805#problem/K
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//      贪心
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 2e3+20;
int a[N][N];void solve()
{int n,m; cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}map<int,int> mp;//用于统计每个颜色在一列中最多有几个连续的for(int i=1;i<=m;i++){int cnt=1;for(int j=2;j<=n;j++)//从第二行开始分别跟第一行的比较找到有几个连续的颜色{//至于为什么要以第一行为准 因为要想操作次数最少肯定要尽可能上面的不动（留下）下面的移走如果第一行要变的话就需要操作n次if(a[j][i]==a[1][i]) cnt++;elsebreak;//如果不连续就没有用了（相当于是其他颜色了因为中间已经有颜色不同了要想把这个换走就需要把下面的都换走）}mp[a[1][i]]=max(mp[a[1][i]],cnt);//如果有多列的第一行颜色相同了 就必须有一列涂其他颜色 就把这个颜色涂到连续最多的那一列}int ans=0;for(int i=1;i<=m;i++){ans+=n-mp[i];}cout<<ans<<endl;
}signed main()
{IOSint T=1;
//	cin>>T;while(T--) solve(); return 0;
}