2023第二十届浙江省大学生程序设计竞赛-AEFGHIKM
2023第二十届浙江省大学生程序设计竞赛 Problem A. Look and SayProblem B. Master of PolygonProblem C. Shuttle TourProblem D. Master of Both IIIProblem E. Interval SumProblem F. Turn on the LightProblem G. Puzzle: Kus
文章共4,922字 · 阅读需要大约17分钟
一键AI生成摘要，助你高效阅读
问答
·
目录
Problem D. Master of Both III
Problem I. Equation Discovering
Problem M. A Wine and Four Dishes
Problem A. Look and Say
签到题
把连续的字母变成cnt+字母的形式
#include<bits/stdc++.h>
using namespace std;
char a[1005];
void solve()
{
int n;
cin>>n;
cin>>a;
int cnt=1;
char op=a[0];
for(int i=1;i<n;i++)
{
if(op==a[i])
{
cnt++;
}else
{
cout<<cnt<<op;
cnt=1;
op=a[i];
}
}
cout<<cnt<<op;
}
int main()
{
int tn=1;
//cin>>tn;
while(tn--)
{
solve();
}
}Problem B. Master of Polygon
Problem C. Shuttle Tour
Problem D. Master of Both III
Problem E. Interval Sum
签到题
考虑哪些数相加为n，有n，{1，n-1},{2,n-2}.....
对于奇数最后是{n/2,n/2+1}
对于偶数最后的n/2没有与他组成的队，把它放数列的最前/后即可
#include<bits/stdc++.h>
using namespace std;
int n;
void solve()
{
cin>>n;
if(n&1)
{
cout<<n<<" ";
for(int i=1,j=n-1;i<=n/2;i++,j--)
{
cout<<i<<" "<<j<<" ";
}
}else
{
cout<<n/2<<" ";
cout<<n<<" ";
for(int i=1,j=n-1;i<n/2;i++,j--)
{
cout<<i<<" "<<j<<" ";
}
}
}
int main()
{
int tn=1;
//cin>>tn;
while(tn--)
{
solve();
}
}Problem F. Turn on the Light
交互题
n<=1e6,要求询问不超过40次
log(1e6)=20,考虑二分，由于返回的是绝对值，不好判断，那么我们可以直接先询问1-20，这样就可以保证每次询问在答案左边，值加一，否则减一
#include<bits/stdc++.h>
using namespace std;
int n;
void solve()
{
cin>>n;
for(int i=1,op,pre=0;i<=20;i++)
{
cout<<"? "<<i<<endl;
cin>>op;
if(op==pre)
{
cout<<"! "<<i<<endl;
return;
}
pre=op;
}
int l=21,r=1e6,op,pre=20,mid;
while(l<=r)
{
mid=(l+r+1)/2;
cout<<"? "<<mid<<endl;
cin>>op;
if(op==pre)
{
cout<<"! "<<mid<<endl;
return;
}else if(op>pre)
{
l=mid+1;
}else
{
r=mid-1;
}
pre=op;
}
}
int main()
{
int tn=1;
//cin>>tn;
while(tn--)
{
solve();
}
}Problem G. Puzzle: Kusabi
每个节点最多只能保留一个关键点信息,贪心匹配每个节点所有的线索
且如果保留Duan信息应该时应该尽可能短，保留长信息应该尽可能长
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
struct node
{
int id,deep;
bool operator<(const node &o)const
{
//if(deep==o.deep)return id<o.id;
return deep<o.deep;
}
};
int n,m;
int flag[100005];
vector<int>v[100005];
int deep[100005];
int ma=0;
vector<int>deepnode[100005];
multiset<node>C[100005];
multiset<node>D[100005];
multiset<node>T[100005];
void dfs(int x)
{
ma=max(ma,deep[x]);
deepnode[deep[x]].push_back(x);
for(int y:v[x])
{
deep[y]=deep[x]+1;
dfs(y);
}
}
void solve()
{
cin>>n;
int cnt=0;
for(int i=1;i<n;i++)
{
int id,fa;
string s;
cin>>id>>fa>>s;
v[fa].push_back(id);
if(s[0]=='C')flag[id]=3,cnt++;
if(s[0]=='T')flag[id]=2,cnt++;
if(s[0]=='D')flag[id]=1,cnt++;
}
dfs(1);
vector<pii>ans;
for(int de=ma;de>=0;de--)
{
for(int x:deepnode[de])
{
for(int y:v[x])
{
for(node c:C[y])
{
C[x].insert(c);
}
for(node d:D[y])
{
D[x].insert(d);
}
for(node t:T[y])
{
T[x].insert(t);
}
}//以上for合起来最多遍历N次
if(flag[x]==1)D[x].insert({x,de}) ;
if(flag[x]==2)T[x].insert({x,de}) ;
if(flag[x]==3)C[x].insert({x,de}) ;
//每个节点最多只能保留一个关键点信息
auto j=C[x].begin();
//bug在这，保留短的应该时最短的，保留长的应该是最长的
// 234 56 留 2
// 23 456 留6
while(j!=C[x].end()&&D[x].size()>0)
{
auto i=D[x].lower_bound({j->id,j->deep});
if(i!=D[x].begin())i=prev(i);
else
{
j++;
continue;
}
if(i->deep<j->deep)
{
ans.push_back({j->id,i->id});
j=C[x].erase(j);
D[x].erase(i);
}else j++;
}
auto k=T[x].begin();
while(k!=T[x].end())
{
auto ne=next(k);
if(ne!=T[x].end())
{
if(k->deep==ne->deep)
{
ans.push_back({k->id,ne->id});
k=T[x].erase(k);
k=T[x].erase(k);
}else k=ne;
}else break;
}
if(D[x].size()+T[x].size()+C[x].size()>1||(x==1&&D[x].size()+T[x].size()+C[x].size()!=0))
{
cout<<"NO"<<endl;
return;
}
}
}
cout<<"YES"<<endl;
for(auto i:ans)
{
cout<<i.x<<" "<<i.y<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tn=1;
//cin>>tn;
while(tn--)
{
solve();
}
return 0;
}Problem H. Puzzle: Tapa
一个线索点周围的炸弹要联通，可以发现只有外围一圈的点不连接里面的点才是不连通的，
我们先假设全是炸弹，那么考虑外围一圈的点做一个二分图，里面全部的点做一个二分图，
二分图连接表示这个位置不是炸弹
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
#define urd uniform_real_distribution
int n,m;
char s[110][110];
char ss[110][110];
string ANS="";
vector<int>v[10005];
int dix[]={1,-1,0,0};
int diy[]={0,0,1,-1};
int f[10005];
int zhi[10005];
bool finds(int x)
{
for(int y:v[x])
{
if(!f[y])
{
f[y]=1;
if(zhi[y]==0||finds(zhi[y]))
{
zhi[y]=x;
zhi[x]=y;
return 1;
}
}
}
return 0;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=2*n-1;i++)
{
cin>>(s[i]+1);
for(int j=1;j<=2*m-1;j++)
{
if((i==1||i==2*n-1)&&(j==1||j==2*m-1))ss[i][j]='3';
else if (i==1||i==2*n-1||j==1||j==2*m-1)ss[i][j]='5';
else ss[i][j]='8';
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[2*i-1][2*j-1]!=ss[2*i-1][2*j-1])
{
ans++;
if((i+j)%2!=0)continue;
int st=0,ed=4;
if(i==1||i==n||j==1||j==m)
{
if((i==1||i==n)&&(j>1&&j<m))st=2;
if((j==1||j==m)&&(i>1&&i<n))ed=2;
}
for(int k=st;k<ed;k++)
{
int tx=i+dix[k];
int ty=j+diy[k];
if(tx<1||tx>n||ty<1||ty>m)continue;
if(s[2*tx-1][2*ty-1]==ss[2*tx-1][2*ty-1])continue;
if((i==1||i==n||j==1||j==m)&&!(tx==1||tx==n||ty==1||ty==m))continue;
if(!(i==1||i==n||j==1||j==m)&&(tx==1||tx==n||ty==1||ty==m))continue;
v[(i-1)*m+j].push_back((tx-1)*m+ty);
}
}
}
}
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[2*i-1][2*j-1]!=ss[2*i-1][2*j-1]&&(i+j)%2==0)
{
memset(f,0,sizeof f);
if(finds((i-1)*m+j))
{
cnt+=2;
}
}
}
}
if(cnt==ans)
{
cout<<"YES"<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i+j)%2==0&&s[2*i-1][2*j-1]!=ss[2*i-1][2*j-1])
{
int tx=(zhi[(i-1)*m+j]-1)/m+1;
int ty=(zhi[(i-1)*m+j]-1)%m+1;
s[2*i-1+(tx-i)][2*j-1+(ty-j)]='#';
}
}
}
for(int i=1;i<=2*n-1;i++)
{
for(int j=1;j<=2*m-1;j++)
{
if(s[i][j]>='0'&&s[i][j]<='9')
{
ss[i][j]=s[i][j];
}else if(s[i][j]=='.')
{
ss[i][j]='#';
}else
{
ss[i][j]='.';
}
}
cout<<ss[i]+1<<endl;
}
}else
{
cout<<"NO";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tn=1;
//cin>>tn;
while(tn--)
{
solve();
}
return 0;
}Problem I. Equation Discovering
运算符复杂度<=9 ,那么x的个数<=5
我们dfs后缀表达式，就可以避免()的讨论
最后对符合要求的后缀表达式转换成中缀表达式输出即可
题目还要求了被除数不会小于0.02，且表达式运算结果与答案误差不超过1e-3
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
typedef long long ll;
#define endl '\n'
#define pii pair<int,int>
#define x first
#define y second
int n,top;
double x[30],y[30];
char st[1005];
double a[30][30];
bool jisuan()
{
//cout<<st+1<<endl;
int top1=0;
for(int i=1;i<=top;i++)
{
if(st[i]=='x')
{
++top1;
for(int j=1;j<=n;j++)
{
a[top1][j]=x[j];
}
}else if(st[i]=='+')
{
for(int j=1;j<=n;j++)
{
a[top1-1][j]+=a[top1][j];
}
top1--;
}else if(st[i]=='-')
{
for(int j=1;j<=n;j++)
{
a[top1-1][j]-=a[top1][j];
if(isnanf(a[top1-1][j]))return 0;
}
top1--;
}else if(st[i]=='*')
{
for(int j=1;j<=n;j++)
{
a[top1-1][j]*=a[top1][j];
}
top1--;
}else if(st[i]=='/')
{
for(int j=1;j<=n;j++)
{
if(abs(a[top1][j])<0.02)return 0;
a[top1-1][j]/=a[top1][j];
}
top1--;
}else if(st[i]=='s')
{
for(int j=1;j<=n;j++)
{
a[top1][j]=sin(a[top1][j]);
}
}else if(st[i]=='c')
{
for(int j=1;j<=n;j++)
{
a[top1][j]=cos(a[top1][j]);
}
}
}
for(int i=1;i<=n;i++)
{
if(abs(a[1][i]-y[i])/max(1.0,abs(y[i]))>0.001)
{
return 0;
}
}
//cout<<a[1][1]<<" "<<a[1][2]<<" "<<a[1][3]<<endl;
return 1;
}
bool dfs(int x,int sum,int cnt)//dfs出后缀表达式---x个数<=5，运算符复杂度<=9，数字栈目前大小
{
if(cnt==1)//此后缀表达式可以计算完
{
//cout<<cnt<<" "<<top<<" ";
if(jisuan())return 1;
}
if(cnt>=2&&(9-sum)/2>=cnt-1)//可以添加二目运算符
{
st[++top]='+';
if(dfs(x,sum+2,cnt-1))return 1;
st[top]='\0';
top--;
st[++top]='*';
if(dfs(x,sum+2,cnt-1))return 1;
st[top]='\0';
top--;
st[++top]='-';
if(dfs(x,sum+2,cnt-1))return 1;
st[top]='\0';
top--;
st[++top]='/';
if(dfs(x,sum+2,cnt-1))return 1;
st[top]='\0';
top--;
}
if(cnt>=1&&sum<=8-cnt+1)//可以添加单目运算符
{
st[++top]='s';
if(dfs(x,sum+1,cnt))return 1;
st[top]='\0';
top--;
st[++top]='c';
if(dfs(x,sum+1,cnt))return 1;
st[top]='\0';
top--;
}
if(x<=5)
{
st[++top]='x';
if(dfs(x+1,sum,cnt+1))return 1;
st[top]='\0';
top--;
}
return 0;
}
void solve()
{
cin>>n;
int f=0;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
if(y[i]>0.001)f=1;
}
if(!f)
{
cout<<"x-x"<<endl;
return;
}
top=0;
int ans=dfs(0,0,0);
if(ans==0)//wa 9,此时tle没跑出答案
{
while(1);
}
//后缀表达式转中缀表达式
string s[1005];
int top1=0;
for(int i=1;i<=top;i++)
{
if(st[i]=='x')
{
s[++top1]="x";
}else if(st[i]=='+')
{
s[top1-1]="("+s[top1-1]+"+"+s[top1]+")";
top1--;
}else if(st[i]=='-')
{
s[top1-1]="("+s[top1-1]+"-"+s[top1]+")";
top1--;
}else if(st[i]=='*')
{
s[top1-1]="("+s[top1-1]+"*"+s[top1]+")";
top1--;
}else if(st[i]=='/')
{
s[top1-1]="("+s[top1-1]+"/"+s[top1]+")";
top1--;
}else if(st[i]=='s')
{
s[top1]="sin("+s[top1]+")";
}else if(st[i]=='c')
{
s[top1]="cos("+s[top1]+")";
}
}
cout<<s[1];
}
int main()
{
IO;
int tn = 1;
//cin >> tn;
while(tn--)
{
solve();
}
return 0;
}
Problem J. Stage Clear
Problem K. Lazy but Diligent
n个楼，m条路，q个课程，在t时刻必须回寝食且路上休息时间合计m时
n<=400，先floyd跑出任意2栋楼直接最短路
q<=400,考虑n^3方dp，dp[i][j]，表示已经上了i个课以第j个课为结尾时最大休息时长
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
struct node
{
ll a,b;
int p;
}ke[500];
int n,m,q,t,s;
ll dp[500][500];
ll dp2[500][500];
void solve()
{
cin>>n>>m>>q>>t>>s;
for(int i=1;i<=400;i++)
{
for(int j=1;j<=400;j++)
{
dp[i][j]=1e12;
dp2[i][j]=-1e12;
}
}
for(int i=1;i<=400;i++)
{
dp[i][i]=0;
}
for(int i=1,x,y;i<=m;i++)
{
ll l;
cin>>x>>y>>l;
dp[x][y]=dp[y][x]=min(dp[x][y],l);
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
int ans=0;
for(int i=1;i<=q;i++)
{
cin>>ke[i].a>>ke[i].b>>ke[i].p;
if((t-ke[i].b-dp[1][ke[i].p])>=0&&(ke[i].a-dp[1][ke[i].p])>=0)//能在t时刻会回去，并且能去上课
{
dp2[1][i]=(t-ke[i].b-dp[1][ke[i].p])+(ke[i].a-dp[1][ke[i].p]);
if(dp2[1][i]>=s)ans=1;
}
}
for(int k=2;k<=q;k++)
{
for(int i=1;i<=q;i++)
{
ll hou=t-ke[i].b-dp[1][ke[i].p];
if(hou<0)continue; //不能赶回去
for(int j=1;j<=q;j++)
{
if(i!=j&&ke[i].a>=ke[j].b+dp[ke[i].p][ke[j].p]&&dp2[k-1][j]>=s)//可以从j赶到i上课
{
ll qian=dp2[k-1][j]-(t-ke[j].b-dp[1][ke[j].p]); //前面的dp要减去最后回到寝室睡觉的时间
ll zhong=ke[i].a-ke[j].b-dp[ke[i].p][1]-dp[1][ke[j].p];//看看中途能不能回去睡觉
if(zhong<0)zhong=0;//不回去睡觉
dp2[k][i]=max(dp2[k][i],qian+zhong+hou);
}
}
if(dp2[k][i]>=s)ans=k;
}
}
cout<<ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tn=1;
//cin>>tn;
while(tn--)
{
solve();
}
return 0;
}Problem L. Barkley
Problem M. A Wine and Four Dishes
n个物品，最少取多少个可以使物品的x，y值之和超过需求的x，y
x<=1,那么当物品里没有x==1的一定不行，否则减去一个x=1中y最大的物品
然后按y大小从大往下取即可
#include<bits/stdc++.h>
using namespace std;
int n,x,y;
struct node
{
int a,b;
bool operator<(const node &o)const
{
return b>o.b;
}
}a[40];
void solve()
{
cin>>n>>x>>y;
int you1=-1;
for(int i=1;i<=n;i++)
{
cin>>a[i].a>>a[i].b;
if(a[i].a)
{
you1=max(you1,a[i].b);
}
}
sort(a+1,a+n+1);
int ans=0;
if(x)
{
if(you1!=-1)
{
y-=you1;
ans=1;
for(int i=1;i<=n&&y>0;i++)
{
if(a[i].a==1&&a[i].b==you1)
{
you1=-1;
}else
{
ans++;
y-=a[i].b;
}
}
}else
{
y=1000;
}
}else
{
ans=0;
for(int i=1;i<=n&&y>0;i++)
{
ans++;
y-=a[i].b;
}
}
//cout<<y<<endl;
if(y>0)
{
cout<<"IMPOSSIBLE";
}else
{
cout<<ans;
}
}
int main()
{
int tn=1;
//cin>>tn;
while(tn--)
{
solve();
}
}
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
12
0- 0
已为社区贡献1条内容
所有评论(0)