机构CSP-S第三次模拟赛wyh补题报告
Programming_Konjac
·
·
个人记录
前言
这是我参加 kdy 的第 3 次模拟赛，成绩达到了第一次到第三次的最好成绩。
模拟赛情况
我的成绩（悲）
T1
题面
题目大意
1. 两个数字相差 $1$。
2. 两个数字同为奇数或偶数。
求最后是否能凑出这样的配对方案，使其两两配对。
### 赛时思路
首先，统计奇数和偶数的个数，记为 $t_0,t_1$。
若 $t_0\equiv 0\pmod 2$ 且 $t_1\equiv 0\pmod 2$，则输出 `YES`。
因为 $n$ 为偶数，所以说若 $t_0$ 为偶数，则 $t_1$ 必为偶数，$t_0$ 是奇数同理。
所以若不满足上述条件，则一定是 $t_0\equiv 1\pmod 2$ 且 $t_1\equiv 1\pmod 2$。
而我们发现，若两两配对的数相差 $1$，则这两个数必定是一个奇数或偶数。
所以在此类情况下，若存在 $|a_x-a_y|=1(1\le x,y \le n,x\ne y)$ 的情况，则必定可以凑成，因为这两个配对之后，奇数和偶数都会减少 $1$ 个，此时偶数和奇数的个数都为偶数了，输出 `YES`。
若上述成立条件都不满足，则输出 `NO`。
### 赛时代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n;
cin>>n;
int a[10005];
int tong[5]={0};
for(int i=1; i<=n; i++){
cin>>a[i];
tong[a[i]&1]++;
}
sort(a+1,a+n+1);
for(int i=1; i<n; i++){
tong[0]=(tong[0]+2)%2;
tong[1]=(tong[1]+2)%2;
if(tong[0]==0&&tong[1]==0){
cout<<"YES\n";
return;
}
if(a[i]+1==a[i+1]){
tong[a[i]&1]--;
tong[a[i+1]&1]--;
i++;
}
}
tong[0]%=2;
tong[1]%=2;
if(tong[0]==0&&tong[1]==0) cout<<"YES\n";
else cout<<"NO\n";
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
freopen("homogeneousArray.in","r",stdin);
freopen("homogeneousArray.out","w",stdout);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
```
## T2
### 题面
### 题面大意
给
### 赛时思路
### 赛时代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool check(string s){
int cnt=0;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
cnt++;
}
else{
if(!cnt){
return 0;
}
cnt--;
}
}
if(!cnt) return 1;
else return 0;
}
void solve(){
string s;
cin>>s;
int n=s.size();
int cnt1=0,cnt2=0;
for(int i=0;i<n;i++){
if(s[i]=='(') cnt1++;
else cnt2++;
}
if(cnt1!=cnt2){
cout<<"No\n";
return;
}
cnt1>>=1;
int l1=0,l2=0,n1=0,n2=0;
for(int i=0; i<n; i++){
if(s[i]=='('){
if(n1<cnt1){
l1++;
n1++;
}
else{
if(l2==0){
cout<<"No\n";
return;
}
l2--;
}
}
else{
if(n2<cnt2-cnt1){
n2++;
l2++;
}
else{
if(l1==0){
cout<<"No\n";
return;
}
l1--;
}
}
}
if(l1==0&&l2==0){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
freopen("V.in","r",stdin);
freopen("V.out","w",stdout);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
I think this solution can solve this problem
*/
```
## T3
### 题面
### 题面大意
一个地图，$3$ 种地板，求最短时间。
冰（`.`）：保持原速度，但是方向不可改变。
石（`#`）：方向可改变，但是每走一格的时间加 $1$。
奖（`G`）：最终去的地方。
如果中间滑出地图了，则视为无法到达。
求每个点到奖励的最短时间。
### 赛时思路
连边，与题解思路一样。
把二维数组拍成一维数组。
然后跑 dijkstra，一开始定一个值（从终点开始搜，所以我们不知道到最后他每走一个的时间是多少，所以定义一个 $8000$ 作为初始时间，每次经过一个石这个时间减 $1$），然后普通 $dijkstra$，算步数和最终的速度，然后计算最终的时间，输出。
### 赛时代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int h,w;
ll dis[640000];
int bushu[640000],kkc[640000];
bool vis[640000];
char c[800][800],a[640000];
struct node{
int data,next,w;
}G[2555555];
int head[640005],cnt=0;
void add(int x,int y,int z){
swap(x,y);
G[++cnt].data=y;
G[cnt].w=z;
G[cnt].next=head[x];
head[x]=cnt;
}
#define pii pair<long long,pair<int,int> >
void dijkstra(int s){
for(int i=1; i<=h*w; i++) dis[i]=114514114514191981;
memset(bushu,0x3f3f3f3f,sizeof bushu);
priority_queue<pii,vector<pii>,greater<pii> > pq;
pq.push({0,{8000,s}});
dis[s]=bushu[s]=0;
kkc[s]=8000;
vis[s]=1;
while(!pq.empty()){
pii temp=pq.top();
pq.pop();
int u=temp.second.second,k=temp.second.first;
for(int i=head[u];i;i=G[i].next){
int v=G[i].data,w=G[i].w;
if(vis[v]) continue;
ll new_dis=dis[u]+1ll*(k-1)*1ll*w;
int new_bushu=bushu[u]+w;
if(new_dis-new_bushu*1ll*(k-2)<dis[v]-bushu[v]*(kkc[v]-1)){
vis[v]=1;
dis[v]=new_dis;
bushu[v]=new_bushu;
kkc[v]=k-1;
pq.push({new_dis-new_bushu*1ll*(k-2),{k-1,v}});
}
}
}
}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
freopen("U.in","r",stdin);
freopen("U.out","w",stdout);
cin>>h>>w;
int sx,sy;
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
cin>>c[i][j];
a[i*(w-1)+j]=c[i][j];
if(c[i][j]=='G'){
sx=i;
sy=j;
}
}
}
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
if(c[i][j]=='G'||c[i][j]=='#'){
int temp_i=i-1,temp_j=j;
while(temp_i>=1&&temp_j>=1){
if(c[temp_i][j]=='#'||c[temp_i][j]=='G'){
add(w*(temp_i-1)+j,w*(i-1)+j,i-temp_i);
break;
}
add(w*(temp_i-1)+j,w*(i-1)+j,i-temp_i);
temp_i--;
}
temp_i=i,temp_j=j-1;
while(temp_i>=1&&temp_j>=1){
if(c[i][temp_j]=='#'||c[i][temp_j]=='G'){
add(w*(i-1)+temp_j,w*(i-1)+j,j-temp_j);
break;
}add(w*(i-1)+temp_j,w*(i-1)+j,j-temp_j);
temp_j--;
}
temp_i=i+1,temp_j=j;
while(temp_i<=h&&temp_j<=w){
if(c[temp_i][j]=='#'||c[temp_i][j]=='G'){
add(w*(temp_i-1)+j,w*(i-1)+j,temp_i-i);
break;
}add(w*(temp_i-1)+j,w*(i-1)+j,temp_i-i);
temp_i++;
}
temp_i=i,temp_j=j+1;
while(temp_i<=h&&temp_j<=w){
if(c[i][temp_j]=='#'||c[i][temp_j]=='G'){
add(w*(i-1)+temp_j,w*(i-1)+j,temp_j-j);
break;
}add(w*(i-1)+temp_j,w*(i-1)+j,temp_j-j);
temp_j++;
}
}
}
}
dijkstra(w*(sx-1)+sy);
for(int i=1; i<=h*w; i++){
if(i%w!=1) cout<<" ";
if(i!=1&&i%w==1) cout<<"\n";
if(dis[i]==114514114514191981) cout<<-1;
else cout<<dis[i]-bushu[i]*(kkc[i]-1);
}
return 0;
}
/*
*/
```
### 正确思路
建图跑最短路，可以只保留那 $C$ 个石砖，这样它们之间至多 $4C$ 条边，对于冰砖上的询问可以枚举它初始往哪个方向滑然后通过第一个碰到的石砖求出答案。
考虑到速度会变，所以要在每个状态下加一维表示当前速度，显然每个石砖至多只会经过一次所以那一维大小为 $O(C)$。这样总点数总边数都是 $O(C^2)$ 的，而且这关于速度那维是个分层图，于是这就只用求 DAG 上最短路，总复杂度 $O(HW+C^2)$。
### 老师正确代码
## T4
### 题面
### 题面大意
找三元组 $x,y,z(x\ne y,y\ne z,x\ne z)$ 的数量，满足 $2$ 个条件。
### 赛时
没时间了，不会做，写了个随机数，喜提 $0$ 分好成绩。
### 老师正确思路
### 老师正确代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,p;
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
srand(time(NULL));
int T;
cin>>T;
while(T--){
int n,q;
cin>>n>>q;
int a[n+5];
for(int i=1; i<=n; i++){
cin>>a[i];
}
sort(a+1,a+n+1);
long long cnt=0;
if(q==1){
cnt++;
for(int i=n-3; i>=1; i--){
if(a[i]+n>=a[n-2]+1) cnt++;
}
for(int i=n-3; i>=1; i--){
if(a[i]+n>=a[n-1]+1) cnt+=n-2-i;
}
for(int i=n-3; i>=1; i--){
if(a[i]+n>=a[n]+1){
long long len=n-1-i;
cnt+=len*(len-1)/2;
}
}
}
else{
if(a[n-2]+n>=a[n-1]+1) cnt++;
int awa=0;
for(int i=n-3; i>=1; i--){
if(a[i]+n>=a[n-1]+1) awa++;
}
cnt+=2*awa+awa*(awa-1)/2;
awa=0;
for(int i=n-1; i>=1; i--){
if(a[i]+n>=a[n]+1){
awa++;
}
}
cnt+=awa*(awa-1)/2*(awa-2)/3;
}
cout<<cnt<<"\n";
}
return 0;
}
/*
*/
```
# 总结
打得不好。
# 题外话
这次模拟赛是数据结构大佬 lxl 讲的。