2021年“图森未来杯”全国程序设计邀请赛 个人题解
C题 Countdown
题目大意：
问 $2021.4.10$ 距离 $2021.10.16$ 有几天
思路解析：
签到题，输出 $189$
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cout<<189<<endl;
}
K题 K-Primes
题目大意：
给出 $l$ ， $k$ ，问在 $[l,l+2k]$ 之间是否存在至少 $k+1$ 个质数
思路解析：
我们会发现区间的长度为 $2k$ ，而质数的分布是越来越稀疏的，所以如果范围大的话，区间中有一半以上的质数是不可能的，所以我们可以直接小范围暴力，大范围直接判断即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int primes[maxn];
bool st[maxn];
int cnt;
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll l,k;
cin>>l>>k;
get_primes(10000);
if(k<=1000){
ll sum=0;
for(int i=l;i<l+2*k;i++){
if(!st[i])sum++;
}
if(sum>=k+1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else cout<<"No"<<endl;
}
I题 I Love You
题目大意：
字符串匹配，问 $a$ 串能否通过删减字符成为 $b$ 串
思路解析：
双指针即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string a,b;
cin>>a>>b;
int j=0;
for(int i=0;i<a.size();i++){
if(a[i]==b[j])j++;
}
if(j==b.size())cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
E题 Edge Game
题目大意：
在一棵树上，给出两个起始点，轮流向相邻节点移动，谁先吃掉对方棋子就赢，都以最优策略移动，问先手是否会赢
思路解析：
显然最优策略一定是两点间树上最短路径，做一次 $dfs$ ,判断奇偶即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=4e5+5;
int h[maxn],nex[maxn],e[maxn],id;
int ans;
int a,b;
void add(int x,int y){
e[++id]=y;
nex[id]=h[x];
h[x]=id;
}
void dfs(int x,int fa,int dis){
if(x==b){
ans=dis;
return ;
}
for(int i=h[x];i;i=nex[i]){
int j=e[i];
if(j==fa)continue;
dfs(j,x,dis+1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
cin>>a>>b;
dfs(a,0,0);
if(ans%2==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
G题 Group QQ Speed
题目大意：
$n$ 个玩家被分为 $m$ 人一组，每位玩家可以 $ban$ 一张地图，同一组玩家共用一张地图且不能是组内 $ban$ 选的地图，问最少需要准备几张地图， $m$ 可以被 $n$ 整除
思路解析：
很直观的考虑三种情况：
$m=n$ 至少需要 $2$ 张地图
$m=1$ 至少需要 $n+1$ 张地图
* 除以上两种情况外，至少需要 $3$ 张地图
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
ll n,m;
cin>>n>>m;
if(m==1)cout<<n+1<<endl;
else if(n==m)cout<<2<<endl;
else cout<<3<<endl;
}
}
D题 Divide
题目大意：
给出 $l_1,r_1,l_2,r_2$ ,令 $a= \prod_{i=l_1}^{r_1}$ , $b= \prod_{i=l_2}^{r_2}$ ,问 $a$ 能否被 $b$ 整除
思路解析：
根据唯一分解定理，我们可以把一个数分解成多个质数的幂乘积的形式，所以我们可以考虑对于a和b，我们枚举他们的每个质数因子，如果a的某个因子数量大于b的因子数量，那么他就一定不可被整除
所以我们就只需求出 $(l_1-1)! , r_1!, (l_2-1)! , r_2!$ ,用前缀和思想判断是否大于即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=1e7+5;
int primes[maxn];
int cnt;
int st[maxn];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int solve(int n, int p){
int ans = 0;
while(n){
ans += n / p;
n /= p;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
get_primes(1e7+5);
int t;
cin>>t;
while(t--){
int ok=0;
int a,b,c,d;
cin>>a>>b>>c>>d;
for(int i=0;i<cnt;i++){
int A=solve(a-1,primes[i]);
int B=solve(b,primes[i]);
int C=solve(c-1,primes[i]);
int D=solve(d,primes[i]);
if(B-A>D-C){
ok=1;
break;
}
}
if(ok==0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
