长沙学院飞腾迈创杯2022年新生赛-题解
长沙学院CCSU2022夏季校赛-题解
比赛指路：快来参加“长沙学院飞腾迈创杯2022年新生赛”~ 比赛时间：2022-05-07 13:30:00 - 2022-05-07 17:30:00，比赛时长：4小时，比赛地址：
https://ac.nowcoder.com/acm/contest/34092
【邀请码：ccsu2022acm】
A. 小贪一手
思路
本题来自于Codeforces Round #653 (Div. 3)A题，指路1374A
贪心，我们要使得 ，且
最大。那么
满足
,所以
。我们令
，题目就成了在
范围内找最大的
的倍数。
是
的
倍，对它进行取整得到倍数
，然后输出
即为答案。数据规模在
范围内，所以使用int型即可，不用考虑数据溢出问题。
STD
#include<iostream>
using namespace std;
int main()
{
int t,n,x,y;
for(cin>>t;t--;cout<<(n-y)/x*x+y<<'\n')
cin>>x>>y>>n;
return 0;
} B. A+B Problem (very easy)
思路
一个很简单的模拟题，考察了对STL_map的运用（当然别的形如字符串数组的东西也可以）。
出题人因为这道题被锐评了......，感谢eroengine同学提供idea。
我们使用 来满足字符串和数字之间的键值对应，在处理输入输出字符串的时候，不难发现
和
字符对于答案没有影响，作为连词符，它的作用与加法符号一样。所以我们直接计算每一个字符串所代表的数字和即可。
有人吐槽本题是码农题，可是这题可以把备注中的内容复制了用一个新的形式输出（自己另外写一个转换程序），然后把形如 的28行式子复制进本题的需要提交的代码中就行咯。或者可以选择用正则表达式、文本编辑器等工具实现替换，复制完了单词表题目就很简单了。记得输出
哦。
STD
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
void init()
{
mp["zero"] =0;
mp["one"] =1;
mp["two"] =2;
mp["three"] =3;
mp["four"] =4;
mp["five"] =5;
mp["six"] =6;
mp["seven"] =7;
mp["eight"] =8;
mp["nine"] =9;
mp["ten"] =10;
mp["eleven"] =11;
mp["twelve"] =12;
mp["thirteen"] =13;
mp["fourteen"] =14;
mp["fifteen"] =15;
mp["sixteen"] =16;
mp["seventeen"] =17;
mp["eighteen"] =18;
mp["nineteen"] =19;
mp["twenty"] =20;
mp["thirty"] =30;
mp["forty"] =40;
mp["fifty"] =50;
mp["sixty"] =60;
mp["seventy"] =70;
mp["eighty"] =80;
mp["ninety"] =90;
}
int main()
{
init();
int t,ans;
cin>>t;
while(t--)
{
string s,tmp="";
cin>>s;
s+='+';
ans=0;
for(auto i:s)
{
if(i=='+'||i=='-')
{
ans+=mp[tmp];
tmp="";
continue;
}
tmp+=i;
}
cout<<ans<<endl;
}
return 0;
} C. Alice and Bob
思路
这题就是很经典的一个SG函数题。每次至少取一张，至多取一半。那么当n=1的时候，先手取的人必胜。当n=2的时候最多取1张，然后后手进入n=1的必胜状态。以此类推就可以将所有的必胜/必败态算出来，std跑到了n=1e18的情况，然而实际题目只有n=1e3的数据规模，可以说非常仁慈。至于后面的查询问题，由于是O(1)查询所以影响不大，重点是预处理SG，不会SG的该学学了。
STD
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,bool> h;
ll x,y,k,i,t;
int main()
{
k=2;
while(i+k<=1e18)
{
i+=k;
h[i]=1;
k<<=1;
}
for(cin>>t;t--;)
{
cin>>x;
puts(h[x]?"YES":"NO");
}
return 0;
} D. 进化
思路
题目按照升序放，这题能放在D的位置肯定就证明他不难，但是没啥人写确实搞出题人心态。
可以看到图的大小是n=8，点的数量也最多为8个。我们可以通过输入轻松找出起点位置和所有的得分点位置。然后直接用dfs枚举吃得分点的顺序，一共是种可能。对于枚举到的每个得分点，我们有两个关键信息：你当前所在的位置，你要去的得分点的位置。由于不限步数，所以直接用bfs/dfs去遍历图看能否不经过其他得分点就跑到目标就行。
所以本题就是一个典中典的双搜索嵌套，一个搜索是枚举，另一个搜索是迷宫，都是很经典且很基础的搜索。
STD
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=12;
int n,m,k;//地图的长宽,点的个数
ll ans=1;//答案初始化为1
char mp[N][N];//原地图
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
struct node {
int x,y,op,data;
};//记录得分点信息
vector<node> v;
bool vis[N],p[N][N];
void get_start()//找出起点位置
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]=='S')
{
mp[i][j]='0';
v.push_back({i,j,2,1});//乘1不变
return;
}
}
bool bfs(int sx,int sy,int ex,int ey)//从a能直接走到b吗
{
memset(p,0,sizeof p);
queue<pii> q;
q.push({sx,sy});
while(q.size())
{
auto [x,y]=q.front();
q.pop();
p[x][y]=1;
for(int i=0;i<4;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(tx==sx&&ty==sy)
continue;
if(p[tx][ty])
continue;
if(1<=tx&&tx<=n&&1<=ty&&ty<=m)
{
if(tx==ex&&ty==ey)
return 1;
if(mp[tx][ty]=='0')
q.push({tx,ty});
}
}
}
return 0;
}
void dfs(int now,ll sum)
{
ans=max(ans,sum);
for(int i=1;i<(int)v.size();i++)
{ //如果now能走到i
if(vis[i]==0&&bfs(v[now].x,v[now].y,v[i].x,v[i].y))
{
vis[i]=1;
mp[v[i].x][v[i].y]='0';
if(v[i].op==1)
dfs(i,sum+v[i].data);
else if(v[i].op==2)
dfs(i,sum*v[i].data);
vis[i]=0;
mp[v[i].x][v[i].y]='S';
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
get_start();//找出起点位置
for(cin>>k;k--;)//输入k个得分点
{
int x,y,op,data;
cin>>x>>y>>op>>data;
mp[x][y]='S';//修改地图为S
v.push_back({x,y,op,data});
}
dfs(0,ans);//起点为0号得分点
cout<<ans<<endl;
return 0;
} E. 防疫物资
思路：
本题考察知识点：树的直径。
改编自算法竞赛指南原题《巡逻》，原题链接：350. 巡逻 - AcWing题库
先考虑的情况，即不能新建道路，要从根节点出发经过所有点并最终回到根节点，那么所有边都至少需要经过两次。
证明：对于任意边 到达
节点的路径唯一
经过一次 最终回到根节点
所以任意边都需要经过至少两次，答案为
.
而题中给出新建一条道路的要求 可以理解为你可以将任意两点之间的路程缩短为 即这新道路两端之间的路径不需要经过两次 而是经过一次以后走新建道路即可。以此为贪心依据选取树上距离最远的两个端点建立道路即可(即树的重心)。设树的直径为
最终答案为
STD
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
struct Edge
{
int to,nex,w;
}e[N << 1];
int head[N],tot;
void add(int to,int from)
{
e[++ tot].w = 1;
e[tot].to= to;
e[tot].nex = head[from];
head[from] = tot;
}
int dis[N],root;
void dfs(int u,int fa)
{
if(dis[0] < dis[u])
{
dis[0] = dis[u];
root = u;
}
for(int i = head[u];i;i=e[i].nex)
{
int v = e[i].to;
if(v == fa) continue ;
dis[v] = dis[u] + e[i].w;
dfs(v,u);
}
}
int n,k;
void solve()
{
cin >> n;
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
add(u,v); add(v,u);
}
dfs(1,1);
dis[root] = 0;
dfs(root,root);
cout << (n - 1) * 2 - dis[0] + 1;
return ;
}
int main()
{
solve();
return 0;
}
对原题有兴趣的同学也可以自行选做。相比原题此题已经是改编后的弱化版了。原题中 对于
的情况涉及到环的交集，求存在负权边的树上直径等知识，树的直径也用到了两种求法。下面以给出原题的ac代码，题解以注释的形式给出。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
/*
k = 0 如果不修建新边 那么每条边都需要经过两遍 res = (n - 1) * 2;
k = 1 可以修建一条边 可以理解为将两点之间距离缩短到1 那么贪心的将最长路径(即树的直径)
端点之间链接到一起形成一个环 环上的道路只需要经过一遍 res = (n - 1) * 2 + 1(新修道路) - L1(直径)
重点 k = 2
按照的k = 1的情况 找到树上的第二直径是否可行 这时需要分情况讨论
1.若两条直径形成的环的边不存在交集 那么此情况就是简单的复制k = 1的情况 res = (n - 1) * 2 + 1 + L1 + 1 + L2
2.存在交集的情况就不能直接简单的减去 因为新修的边必须经过且只能经过一次，那么交集的那部分边必须经过两遍，反而劣于k = 1的情况
对于处理k = 2的情况我们可以先求出树上的直径(两遍dfs,bfs) 并且将路径上的边权置为-1 再求第二直径
边权置为-1的合理性 ：
若是情况1 那么两个环互不影响第一个环的边权置为-1对结果不影响
情况2 计算第二直径路径长度时因为交集为-1，也符合交集的边计算两遍的情况(抵消计算第一直径时减去)
最后值得注意的是第二遍求直径时因为图中存在负数边权 不能使用dfs,bfs的方法求解，应使用DP
*/
struct Edge
{
int to,nex,w;
}e[N << 1];
int head[N],tot;
void add(int to,int from)
{
e[++ tot].w = 1;
e[tot].to= to;
e[tot].nex = head[from];
head[from] = tot;
}
int dis[N],fa[N],id[N],root;
void dfs(int u)//求直径
{
if(dis[0] < dis[u])
{
dis[0] = dis[u];
root = u;
}
for(int i = head[u];i;i=e[i].nex)
{
int v = e[i].to;
if(v == fa[u]) continue ;
fa[v] = u; dis[v] = dis[u] + 1; id[v] = i;//记录edge中的存储编号
dfs(v);
}
}
int n,k;
void change(int tmp)//改变直径上的边权
{
while(root != tmp)
{
e[id[root]].w = -1;
e[id[root] + ( (id[root] & 1) ? 1 : -1)].w = -1;//找到u -> v的编号即可找到v -> u编号 因为两种成对存入的edge
root = fa[root];
}
//dis[0] = 0;
/*在最坏的情况下,即第二直径与第一直径的边完全重合,对路程是负优化的情况。
我们可以对两个环的起始点进行调整达到不存在边的交集,并且恰好包括第一直径的所有边。所以dis[0]赋值为0*/
dis[0] = 0;
for(int i=1;i<=n;i++) dis[i] = -n;
}
void dfs(int u,int f)//找第二直径
{
for(int i=head[u];i;i=e[i].nex)
{
int v = e[i].to;
if(v == f) continue ;
dfs(v,u);
/*
dis[0] = max(dis[0],dis[u] + dis[v] + e[i].w);每次转移都带有边权e[i].w
只考虑了儿子到另一儿子的情况 ，而没有考虑单儿子的情况 单根节点的情况因为dis[0] = 0 无须考虑
设根为u,儿子节点为v1,v2,……,vk
那么只考虑了vi -> u -> vj的情况 没有考虑u -> vi的情况
*/
dis[0] = max(dis[0],dis[u] + dis[v] + e[i].w);
dis[u] = max(dis[u],dis[v] + e[i].w);
}
dis[u] = max(dis[u],0);
dis[0] = max(dis[0],dis[u]);//因为存在负边权所以可能存在非拼接的情况 即单儿子的情况
}
void solve()
{
cin >> n >> k;
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
add(u,v); add(v,u);
}
int ans = (n - 1) * 2 + k,tmp;
dfs(1);
dis[root] = 0; fa[root] = 0; dis[0] = 0; tmp = root;
dfs(root);
ans -= dis[0];
if(k == 2)
{
change(tmp);
dfs(1,0);
ans -= dis[0];
}
cout << ans;
return ;
}
int main()
{
solve();
return 0;
}
/*
单链
5 2
1 2
2 3
3 4
4 5
7 2
1 2
1 3
2 4
2 5
3 6
3 7
两个环重叠有负权
12 2
1 2
2 3
3 4
4 5
4 9
5 6
6 7
7 8
9 10
10 11
11 12
*/ F. 有挂
思路
线段树懒标记，具体的过些时候完善
STD
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,x;
namespace seg_tree
{
const int N=1e5+10;
struct node
{
int l,r;
ll sum;
ll lazyp;
}t[N<<2];
#define mid (t[k].l+t[k].r>>1)
#define check (l<=t[k].l&&t[k].r<=r)
void f(int k,ll v)
{
t[k].sum+=1ll*(t[k].r-t[k].l+1)*v;
t[k].lazyp+=v;
}
void pushdown(int k)
{
f(k<<1,t[k].lazyp);
f(k<<1|1,t[k].lazyp);
t[k].lazyp=0;
}
void pushup(int k)
{
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
void build(int k,int l,int r)
{
t[k].l=l;
t[k].r=r;
t[k].sum=0;
t[k].lazyp=0;
if(l==r)
{
return ;
}
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(int k,int l,int r,ll v)
{
if(check)
{
f(k,v);
return ;
}
pushdown(k);
if(l<=mid)modify(k<<1,l,r,v);
if(r>mid)modify(k<<1|1,l,r,v);
pushup(k);
}
ll query(int k,int l,int r)
{
if(check)
{
return t[k].sum;
}
ll ans=0;
pushdown(k);
if(l<=mid)ans+=query(k<<1,l,r);
if(r>mid)ans+=query(k<<1|1,l,r);
return ans;
}
}
int main()
{
cin>>n>>m>>x;
seg_tree::build(1,1,n);
while(m--)
{
ll op,l,r,va;
cin>>op>>l>>r;
if(op==1)
{
cin>>va;
va=va/x+(va%x>0);
seg_tree::modify(1,l,r,va);
}
else
{
cout<<seg_tree::query(1,l,r)<<endl;
}
}
} G. 鸡你太美
思路
本题是基础的状压dp,本质上是线性dp,我们知道dp的基本要素就是状态,状态的转移,状压dp是利用状压的思想将难以表示的状态用二进制或者其他一些形式表达出来,然后进行转移,因此一般状态的数据一般比较小.该题所给的状态,经过分析后,了解到是连续的m天,且m最大为8,就想到用二进制的状态表示这连续的m天的打球的状态.例如连续五天内,在第一天和第三天睡觉,可以表示为10100,同理,01000表示在第二天打球.
知道如何表示状态了,就要考虑如何进行转移了.也就是我们要进行m天之后的延伸.若我们寻找区间1-m的后置状态,可以想到我们会找2-(m+1)的天数打球状态.如何将两者联系?其实只要把1-m天的后缀的(m-1)位二进制数的情况和2-(m+1)的前缀(m-1)位数的情况相比较.若两者相等,就可以往后延伸.
例如:
10001
00011
前者的后m-1位和后者的前m-1位相等,就说明可以进行转移.此时还要注意后者的最后一位情况来判断当前天要不要吧开心值加上去.直接最后去最大值即可
STD
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#define int long long
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
int f[N][1<<8];
//dp数组f[i][j]的意思为前i天的后m天的打球状态为多少
int happy[N];
bool check(int x,int y){
int X = x>>1;
while(X){
if((X&1)==(y&1)){
X>>=1;
y>>=1;
}
else{
return false;
}
}
return true;
}
signed main()
{
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&happy[i]);
vector<int>play_day;
for(int i=0;i<(1<<m);i++)
{
int ans=0,days=i,temp=0;
while(days)
{
if(days&1)
temp++;
days>>=1;
}
if(temp<=m/2)
play_day.push_back(i);
}
/*
预处理合法的情况,合法的情况是指连续m天有一半时间打球,也就是在2^m的情况中二进制位上有<=m/2个1的情况.
*/
for(int i=0;i<play_day.size();i++)
{
int temp=play_day[i];
int tot=1;
while(temp)
{
if(temp&1)
f[m][play_day[i]]+=happy[tot];
temp>>=1;
tot++;
}
}
/*预处理初始状态的happy值,看每个合法状态的happy值,第几位为1就表示今天打了球,加上happy值*/
vector<int>ve[1<<8];
for(int j=0;j<play_day.size();j++)
{
for(int k=0;k<play_day.size();k++)
{
int x=play_day[j],y=play_day[k];
if(check(x,y)){
ve[x].push_back(y);
}
}
}
/*
预处理后继状态,将符合我上文说的前一种状态的后m-1位和后继状态的前m-1位相比较,如果相等那么两者能进行转换
*/
for(int i=m+1;i<=n;i++)
{
for(int j=0;j<play_day.size();j++)
{
for(int k=0;k<ve[play_day[j]].size();k++)
{
int x=play_day[j];
int y=ve[play_day[j]][k];
if(y>>(m-1)==1)
f[i][y]=max(f[i-1][x]+happy[i],f[i][y]);
else
f[i][y]=max(f[i-1][x],f[i][y]);
}
}
}
/*
状态转移.当新的状态最后一位为1表示该天打了球,加上happy值.这的注意的是这里转移要求最大值,需要时max,不是求方案数或者最小值
*/
int maxx=-1;
for(int i=0;i<play_day.size();i++)
{
if(f[n][play_day[i]]>maxx)
maxx=f[n][play_day[i]];
}
printf("%d",maxx);
return 0;
} H.爱美之心人皆有之
不小心原到牛客练习赛90C上去了，可以移步练习赛题解区。
I. 签签签到
思路
这题还蛮好玩的，出个这个活跃一下气氛，感谢沙烬同学提供idea。
本题的题面有5个超链接，在图片下方的4个都是假的超链接，点开后会是这么一句话
这句话应该是每一个CCSU_ACMer共同的梦想。
但是很可惜，本题的答案不是这句话。图片上方有还有一个超链接，点开后是如下字样
你需要做的是在不转义的情况下输出一下字符串，使用R"(STRING)"可以实现字符串不转义输出。
PS.鼠标放在超链接上的时候可以看到下面四个都写了“别点”，最上面那个才有“这是正确答案”。不信你再去试一试！
STD
#include<bits/stdc++.h>
int main()
{
std::cout<<R"(%d%\n")";
} 
拼多多二面21人在聊