# 长沙学院CCSU2022夏季校赛-题解

https://ac.nowcoder.com/acm/contest/34092
【邀请码：ccsu2022acm】

## A. 小贪一手

### 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)

### 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

### 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. 进化

### 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. 防疫物资

### STD

```#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
struct Edge
{
int to,nex,w;
}e[N << 1];
{
e[++ tot].w = 1;
e[tot].to= to;
}
int dis[N],root;
void dfs(int u,int fa)
{
if(dis[0] < dis[u])
{
dis[0] = dis[u];
root = u;
}
{
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;
}
dfs(1,1);
dis[root] = 0;
dfs(root,root);
cout << (n - 1) * 2 - dis[0] + 1;
return ;
}
int main()
{
solve();
return 0;
}
```

```#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
/*
k = 0 如果不修建新边 那么每条边都需要经过两遍 res = (n - 1) * 2;
k = 1 可以修建一条边 可以理解为将两点之间距离缩短到1 那么贪心的将最长路径(即树的直径)

1.若两条直径形成的环的边不存在交集 那么此情况就是简单的复制k = 1的情况 res = (n - 1) * 2 + 1 + L1 + 1 + L2
2.存在交集的情况就不能直接简单的减去 因为新修的边必须经过且只能经过一次，那么交集的那部分边必须经过两遍，反而劣于k = 1的情况

*/
struct Edge
{
int to,nex,w;
}e[N << 1];
{
e[++ tot].w = 1;
e[tot].to= to;
}
int dis[N],fa[N],id[N],root;
void dfs(int u)//求直径
{
if(dis[0] < dis[u])
{
dis[0] = dis[u];
root = u;
}
{
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)//找第二直径
{
{
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;
}
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. 鸡你太美

10001

00011

### 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);
}
/*

*/

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);
}
}
}
/*

*/

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]);
}
}
}

/*

*/

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;
}```

## I. 签签签到

### 思路

PS.鼠标放在超链接上的时候可以看到下面四个都写了“别点”，最上面那个才有“这是正确答案”。不信你再去试一试！

### STD

```#include<bits/stdc++.h>
int main()
{
std::cout<<R"(%d%\n")";
}```

# 近期热帖

• 回复(22) 发表于 2022-06-24 13:28:20
• 回复(32) 发表于 2022-06-24 17:46:06
• 回复(27) 发表于 2022-06-24 16:48:11
• 回复(18) 发表于 2022-06-24 16:15:29
• 回复(3) 发表于 2022-06-24 13:25:20

# 等你来战

• 报名截止时间：2022-06-30 16:00
• 报名截止时间：2022-07-02 16:30
• 报名截止时间：2022-07-18 17:00
• 报名截止时间：2022-07-23 17:00

# 热门推荐

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题