2021年中国大学生程序设计竞赛女生专场
K - 音乐游戏
思路：签到题，数有多少'-'
#include<bits/stdc++.h> using namespace std; #define int long long vector<int>d[5010];int32_t main(){int n;cin>>n;int ans=0;getchar();for(int i=1;i<=n;i++){string s;getline(cin,s);for(int i=0;i<s.length();i++){if(s[i]=='-'){ans++;}}}cout<<ans<<endl;return 0; }
G - 3G网络
思路：签到题，当r无穷大，所有圆所占范围近似相同，那么答案为1/n
#include<bits/stdc++.h> using namespace std; #define int long longint32_t main(){int n;cin>>n;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;}printf("%.15lf",1.0/n);return 0; }
D - 修建道路
思路：签到题，连n-1条边让n个点相通，且连接i和j需要花费max{ak}（i<=k<=j）；对于点i，要与1~i-1连一条边，那么一定是连i-1，若存在ak<ai-1（k<i-1），由于要取max，那么一定取不到ak，若存在ak>ai-1（k<i-1），那么取i-1是最优的，所以i一定是连i-1，且连完一定保证n个点相通。
#include<bits/stdc++.h> using namespace std; #define int long long int a[200010];int32_t main(){int n;cin>>n;int ans=0;for(int i=1;i<=n;i++){cin>>a[i];if(i>=2)ans+=max(a[i],a[i-1]);}cout<<ans<<endl;return 0; }
A - 公交线路
思路：签到题，判断下是否超过范围，在分别判两个方向是否正确
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6;void solve(){int n,x,y;cin>>n>>x>>y;vector<int>a(n+1);for(int i=1;i<=n;++i)cin>>a[i];int k;cin>>k;vector<int>b(k+1);for(int i=1;i<=k;++i)cin>>b[i];bool r=true,l=true;if(x+k>n)r=false;if(x-k<1)l=false;for(int i=1,il=x-1,ir=x+1;i<=k;++i){if(r&&b[i]!=a[ir++])r=false;if(l&&b[i]!=a[il--])l=false;}if(r&&l)cout<<"Unsure";else if((x<y&&r)||(x>y&&l))cout<<"Right";else cout<<"Wrong"; } signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--){solve();}return 0; }
I - 驾驶卡丁车
思路：模拟题，模拟每一步的速度，方向
#include<bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int dx[8]= {-1,-1,0,1,1,1,0,-1}; int dy[8]= {0,1,1,1,0,-1,-1,-1}; int32_t main(){int n,m;cin>>n>>m;string g[55];int sx,sy;for(int i=1;i<=n;++i){string s;cin>>s;g[i]=' '+s;for(int j=1;j<=m;++j)if(g[i][j]=='*')sx=i,sy=j;}int q,v=0,dir=0;cin>>q;string s;cin>>s;for(int i=0;i<q;++i){if(s[i]=='U')v++;else if(s[i]=='D')v=max(v-1,0ll);else if(s[i]=='L')dir--,dir=(dir+8)%8;else dir++,dir%=8;bool ok=false;for(int j=1;j<=v;++j){int x=sx+dx[dir],y=sy+dy[dir];if(dir==0||dir==2||dir==4||dir==6){if(x<1||x>n||y<1||y>m||g[x][y]=='#'){v=0,ok=true;break;}else sx=x,sy=y;}else if(dir==7){if(x<1||x>n||y<1||y>m||g[x][y]=='#'){v=0,ok=true;break;}int x1=sx+dx[dir-1],y1=sy+dy[dir-1];int x2=sx+dx[0],y2=sy+dy[0];if(g[x1][y1]=='#'&&g[x2][y2]=='#'){v=0,ok=true;break;}sx=x,sy=y;}else{if(x<1||x>n||y<1||y>m||g[x][y]=='#'){v=0,ok=true;break;}int x1=sx+dx[dir-1],y1=sy+dy[dir-1];int x2=sx+dx[dir+1],y2=sy+dy[dir+1];if(g[x1][y1]=='#'&&g[x2][y2]=='#'){v=0,ok=true;break;}sx=x,sy=y;}}if(ok)cout<<"Crash! ";cout<<sx<<' '<<sy<<'\n';}return 0; }
C - 连锁商店
思路1：状态dp，由于n<=36，若每个公司都有多个商店，且最多有18个公司需要考虑购买哪个商店的问题，可以用2进制表示有多商店的公司的情况，将多商店的公司离散化到二进制数的位数，（二进制数当前位为1表示该公司已购买，0表示没购买），将多商店的公司离散化成二进制数位数，其他的商店直接购买，那么就可以用dp来求每个景点的最大花费；
fa[i]表示景点i属于哪家公司，w[i]表示公司i的卖价，now[i]表示公司i表示二进制数的位数；
f[i][j]表示第i个景点当前多商店公司的购买情况为j的最大花费，
若第i个景点的公司不含其他商店：f[i][j]=max（f[i][j]，f[k][j]+w[fa[j]]）
否则：若j的now[i]位为0，则f[i][j|（1<<now[i]）]=max（f[i][j|（1<<now[i]）]，f[k][j]+w[fa[j]]）；若j的now[i]位为1，则f[i][j]=max（f[i][j]，f[k][j]）；
B - 攻防演练
思路：将串按每部分至少一个含所有的m个字符划开，（除最后一部分外），如aabc|abc|abbc|c，可以看出答案为4；因为每一部分可以代表构造的串的每一位的所有情况，从前开始每跳一个部分，当跳到r外，跳的次数加一即为构造的最短串长度。可以预处理出位置i后第一个字符j出现的位置，再求出i位置后所有m个字符第一次出现的位置的最大值（即为每一部分的分界线），那么求l~r跳多少步可以线性的跳，但是O（n2）的；
这里可以用倍增，f[i][j]表示从i位置开始跳2j步到达的位置，那么j最大18，j从大到小判断是否跳到r外并对步数进行累加，便可求出答案
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6;void solve(){int m,n;cin>>m>>n;string s;cin>>s;s.insert(s.begin(),' ');vector<vector<int>>f(n+5,vector<int>(30));vector<int>pos(30,n+1);for(int i=0;i<=18;++i)f[n+1][i]=n+1;for(int i=n;i>=0;--i){for(int j=0;j<m;++j)f[i][0]=max(f[i][0],pos[j]);if(i)pos[s[i]-'a']=i;}for(int i=1;i<=18;++i)for(int j=0;j<=n;++j)f[j][i]=f[f[j][i-1]][i-1];int q;cin>>q;while(q--){int ans=0,l,r;cin>>l>>r;l--;for(int i=18;i>=0;--i){if(f[l][i]<=r){l=f[l][i];ans+=1ll<<i;}}ans++;cout<<ans<<'\n';} } signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T=1;//cin>>T;while(T--){solve();}return 0; }
