1. 首页
  2. 文章中心
  3. 训练

GYM 101875 2018 USP-ICMC

75 阅读 0 评论
我是靠谱客的博主 酷酷糖豆，最近开发中收集的这篇文章主要介绍GYM 101875 2018 USP-ICMC，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

周末的一次组队训练，让我再次感觉到自己的菜

题目链接

Problem A

题意：求最大生成树的权值和

题解：可以证明的是，我们每一个人都向接下来的第k个人连边，剩下的连第k-1个人，这样得到的边权和一定是最大的

C++版本一

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
long long n,k,ans;
cin>>n>>k;
long long a=gcd(n,k);
if(a!=1) ans=(n-a)*k+(a-1)*(k-1);
else ans=(n-1)*k;
cout<<ans<<endl;
return 0;
}

Problem B

题意：给你一串长度为n的数，这个数可以将后面的数挪到前面来，如果没有小于最开始的那个数的话就输出YES，否则输出NO

题解：如果后面有数字小于第一个数的话就肯定是NO了，这题的坑点就是如果前面很长一串都相同但是后面有一个比前面相同位置的数小的话也要输出NO，因为n是5e5，我们不可能检查每一个串，其实对于这个字符串，我们可以求出这个数的最小表示法的答案，如果这个字符串的最小表示法的第一个字符不是第一个的话就是NO了

C++版本一

#include<bits/stdc++.h>
using namespace std;
int n;
string s,ss;
int main()
{
cin>>n>>s;
int a,b;
for(int i=0,j=1,k=0;i<n&&j<n&&k<n;){
int t=s[(i+k)%n]-s[(j+k)%n];
if(t==0)k++;
else{
if(t>0) i+=(k+1);
else j+=(k+1);
k=0;
}
if(i==j) j++;
a=i;b=j;
}
int tt= min(a,b);
for(int i=tt; i<tt+n; i++)
ss+=s[i%n];
for(int i=0; i<n; i++)
if(ss[i]<s[i]){
cout<<"No"<<endl;
return 0;
}
cout<<"Yes"<<endl;
return 0;
}

Problem C

题意：

题解：

C++版本一

/*
*@Author:
Agnel-Cynthia
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
//#define DEBUG
#define RI register int
//#define endl "n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1e3+10;
const int M=1e6+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
//int t,n,m,k,p,l,r,u,v;
bool f[M];
ll p[M];
int tot = 0;
std::vector<int> v;
bool vis[3003][1003];
ll dp[3003][1003];
unordered_map<ll, ll> mp;
void init()
{
f[0] = f[1] = 1;
for(int i = 2; i < M; i++)
{
if(!f[i]) p[tot++] = i;
for(int
j = 0; j < tot && i * p[j] < M ; j ++)
{
f[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
}
void add(ll &a, ll b)
{
a += b;
while(a >= MOD) a-=MOD;
}
void gao(ll x)
{
for(int i = 0; i < tot && p[i] * p[i] <= x ; i++)
{
if(x % p[i] == 0)
{
int cnt = 0;
while(x % p[i] == 0) x /= p[i],cnt ++;
mp[p[i]] += cnt;
}
}
if(x > 1) mp[x] ++;
}
long long solves(int pos,int need)
{
if( pos == v.size()) return need == 1;
if(vis[pos][need]) return dp[pos][need] ;
vis[pos][need] = 1;
for(int
i = 0; i <= v[pos]; i++)
{
if(need % (i + 1 ) == 0)
{
add(dp[pos][need], sovles(pos + 1, need / (i+1 )));
}
}
return dp[pos][need];
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
int b, n;
init();
scanf("%d %d",&b,&n);
ll x;
for(int
i = 1; i <= n ; i++)
{
scanf("%lld",&x);
gao(x);
}
for(auto k : mp)
{
v.push_back(k.second);
}
printf("%lldn",solves(0,b));
//cout << "Hello world!" << endl;
return 0;
//#ifdef DEBUG
//
printf("Time cost : %lf sn",(double)clock()/CLOCKS_PER_SEC);
//#endif
}

Problem D

题意：我们最多可以走n步，每一步可以走上下左右，问你从起点走到终点有多少种方法

题解：最小步数移动到目标后，其他正好到达目标点的步数为当前最小步数加2的倍数。

C++版本一

/*
*@Author:
Agnel-Cynthia
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
//int t,n,m,k,p,l,r,u,v;
int main()
{
#ifdef DEBUG
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//scanf("%d",&t);
//while(t--){
ll n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
ll sum1 = abs(y2 - y1) + abs(x2 - x1);
ll sum = n - sum1;
if(x1 == x2 && y1 == y2) cout << n/2 << endl;
else if(sum < 0) cout << 0 << endl;
else cout << sum/2 + 1 << endl;
#ifdef DEBUG
printf("Time cost : %lf sn",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}

Problem E

题意：给你一个长度为n的01串，0表示当天不需要工作，1表示当天需要工作，我初始时有体力值为k，如果连续工作时，我第一天需要耗费的体力值为1，第二天需要耗费的体力值为2，第三天许哟啊耗费的体力值为3，，，以此类推，问我们现在需要从这个01串中最少改变多少个1为0使得我们k个体力值够用

题解：DP

C++版本一

/*
*@Author:
Agnel-Cynthia
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m = 0,k,p = 1,l,r,u,v;
bool checkmin(int &a, int b){return b < a ? a =
b,true:false;}
char str[N];
int f[2][N][N],minn[N][N];
int main()
{
scanf("%d%d",&n,&v);
scanf("%s",str+1);
f[m][0][0] = 0;
for(int i = 1; i<= n; i++)
{
for(int j = 0; j <= i; j++)
{
for(int k = 0; k <= i; k++ )
{
if(str[i] == '0')
{
if(k == 0)
{
f[p][j][0] = minn[i-1][j];
}
else f[p][j][k] = 0x3f3f3f3f;
}
else
{
f[p][j][k] =
0x3f3f3f3f;
if(j && (k == 0)) checkmin(f[p][j][k],minn[i-1][j-1]);
if(k) checkmin(f[p][j][k],f[m][j][k-1]+k);
}
}
minn[i][j] =
0x3f3f3f3f;
for(int
k = 0; k
<= i; k++)
checkmin(minn[i][j],f[p][j][k]);
}
swap(m,p);
}
int ans = INT_MAX;
for(int j = 0; j <= n; ++j)
for(int k = 0; k <= n; ++k)
{
if(f[m][j][k] <= v)
checkmin(ans,j);
}
printf("%dn",ans);
return 0;
}

Problem F

题意：有n个人，每个人如果有喜欢的数，那么他就只喜欢这些数，如果他有讨厌的数，那么他就喜欢除了这个数外的任何数，求有多少个数是这n个人都喜欢的

题解：map记录一下就行，如果没有只喜欢某一些数的人的话，我们就输出1e8-（所有人讨厌的数即可）

C++版本一

/*
*@Author:
Agnel-Cynthia
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int M=100000+10;
const int MOD=1e9+7;
const ll maxn = 1000000000000000000;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
//int t,n,m,k,p,l,r,u,v;
map<ll,ll>mp;
map<ll,ll>mp2;
int main()
{
#ifdef DEBUG
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//scanf("%d",&t);
//while(t--){
ll n;
int op = 0;
cin >> n;
ll ans = 0;
for(ll i = 0; i < n; i++)
{
ll k;
cin >> k;
ll m;
cin >> m;
for(ll i = 0; i < m; i++)
{
ll x;
cin >> x;
if(k == 1)
mp[x]++;
if(k == 2) mp2[x]++;
}
if(k == 1) op ++;
if(k == 2) ans ++;
}
map<ll,ll>::iterator it;
ll sum = 0;
for(it = mp.begin(); it != mp.end(); it++)
{
it -> second += ans ;
// cout << it -> second << endl;
// if(it -> second == n) sum++;
}
for(it = mp2.begin(); it != mp2.end() ; it++)
{
mp[it->first] -= it->second;
}
for(it = mp.begin(); it != mp.end(); it++)
{
// it -> second += ans ;
if(it -> second == n) sum++;
}
if(op == 0)
cout << (ll)(maxn - mp.size()) << endl;
else
cout << sum << endl;
#ifdef DEBUG
printf("Time cost : %lf sn",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}

Problem G

题意：在一条直线上有n辆车，每辆车都有自己的位置和速度，如果后面一辆车撞上前面一辆车时，后面一辆车的速度会变得和前面一辆车一样，问你什么时候不可能有车子相撞

题解：们先将车按照pos的顺序从小到大排序，定义第一辆车为1，从n到1扫一遍，如果在第i个位置的车的速度小于我当前车的速度的话，我当前位置的的车的速度是一定会变成第i个位置的速度，否则的话，我当前位置的车是一定会被撞的，计算出被第i辆车撞的时间保存最大值即可

C++版本一

#include <bits/stdc++.h>
using namespace std;
int n;
struct node
{
int s,v;
}a[100005];
bool cmp(node a,node b)
{
return a.s<b.s;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].s,&a[i].v);
}
sort(a+1,a+1+n,cmp);
int minn=n;
double ans=0;
for(int i=n-1;i>=0;i--){
if(a[i].v<=a[minn].v) minn=i;
else ans=max(ans,(double)(a[minn].s-a[i].s)/(a[i].v-a[minn].v));
}
printf("%.5fn",ans);
return 0;
}

Problem H

题意：有一个密码箱，他有n个数字齿轮，每个齿轮是可以被转动的，有两个人玩起了这个游戏，现在有以下的游戏规则

题解：

C++版本一

在这里插入代码片

Problem I

题意：有一个游戏，现在一共有n个人，给出n个关系，如果第i个人去的话，第a[i]个人也去

题解：若点y是x的祖先，则y肯定回来。一次dfs确定每个点覆盖的区间，若点x的dfs序在y的覆盖区间内，则y肯定会来。

C++版本一

/*
*@Author:
Agnel-Cynthia
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
//#define endl "n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
//int t,n,m,k,p,l,r,u,v;
struct node
{
int l,r;
} S[M];
int a[M];
vector<int> b[M];
int cnt;
dfs (int x)
{
S[x].l = ++cnt;//处理
for(int i = 0; i < b[x].size(); i++) dfs(b[x][i]);//一个人每一个好朋友同等级处理
S[x].r = cnt;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
int n, q;
// cin >> n >> q;
scanf("%d%d",&n,&q);
for(int
i
= 0; i < n; i++)
{
int x;
// cin >> x;
scanf("%d",&x);
if(x == -1) continue ;
//b[x][i] = i;
//存入好朋友
b[x].push_back(i);
a[i] ++;
}
//从根出发，预处理下朋友左右
for(int
i = 0; i < n; i++) if(!a[i]) dfs(i);
while(q--)
{
int u, v;
//cin >> u >> v;
scanf("%d%d",&u,&v);
if((S[v].l <= S[u].l && S[v].r >= S[u].r) == 1)
puts("Yes");
else
puts("No");
}
#ifdef DEBUG
printf("Time cost : %lf sn",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}

Problem J

题意：

题解：

C++版本一

在这里插入代码片

Problem K

题意：

题解：

C++版本一

在这里插入代码片

Problem L

题意：有一个n个点的树，小明从起点出发，问他最多可以经过多少点，每个点不能经过两次

题解：从起点bfs一遍即可

C++版本一

#include <bits/stdc++.h>
using namespace std;
int ans=1;
vector<int>a[100005];
struct node{
int st,de;
} b;
int vis[100005];
queue<node>e;
void bfs(int x){
memset(vis,0,sizeof(vis));
vis[x]=1;
b.st=x;
b.de=1;
e.push(b);
while(!e.empty()){
e.pop();
ans=max(ans,b.de);
int s=b.st;
int t=a[s].size();
b.de++;
for(int i=0; i<t; i++){
if(!vis[a[s][i]]){
vis[a[s][i]]=1;
b.st=a[s][i];
e.push(b);
}
}
b=e.front();
}
return ;
}
int main()
{
int n,x;
cin>>n>>x;
for(int i=1; i<n; i++){
int c,d;
cin>>c>>d;
a[c].push_back(d);
a[d].push_back(c);
}
bfs(x);
cout<<ans<<endl;
return 0;
}

最后

以上就是酷酷糖豆为你收集整理的GYM 101875 2018 USP-ICMC的全部内容，希望文章能够帮你解决GYM 101875 2018 USP-ICMC所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(50)

相关文章

hdu 6153
hdu 6153
gym102798 2020CCPC威海B Labyrinth
gym102798 2020CCPC威海B Labyrinth
HDU 6153 A Secret（扩展KMP算法）原题题意涉及知识及算法代码
HDU 6153 A Secret（扩展KMP算法）原题题意涉及知识及算法代码
[编程题] 寻找第K大
[编程题] 寻找第K大
GYM 101875 2018 USP-ICMC
GYM 101875 2018 USP-ICMC
HDU 6153 A SecretA Secret
HDU 6153 A SecretA Secret
J - Weird Sanchola Gym - 102302J
J - Weird Sanchola Gym - 102302J
L - Clock Master Gym - 102798L
L - Clock Master Gym - 102798L

评论列表共有 0 条评论

立即
投稿
返回
顶部