目录
A. Goodbye, Ziyin!
题意为给我们一棵树，问有多少个节点可以当作二叉树根节点
首先二叉树中每个节点最多有3个度，如果有一个节点度大于3了，那么这棵树就不是二叉树
直接输出0即可
反之输出度小于等于2的点的数量即可
代码如下
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
#define double long double
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e6+10;
vector<int> v[N];
signed main()
{
int T;
cin>>T;
fer(i,1,T-1){
int a,b;
input(a,b);
v[a].pb(b);
v[b].pb(a);
}
int ans=0;
fer(i,1,T){
if(v[i].size()>3){
ans=0;
break;
}
else if(v[i].size()>=0&&v[i].size()<3){
ans++;
}
}
cout<<ans<<endl;
}D. Period
题意为给我们一个字符串，问将一个字母变成#后，有多少个不同的前缀等于后缀
首先#肯定没有对应匹配的字母，我们只需要考虑#之前的或之后的有几个前缀等于后缀即可
算下哈希值，前缀一下
代码如下
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
#define double long double
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1e6+10;
const int p=131;
int hs[N];
int bin[N];
string s;
int ans[N];
int n;
void shash()
{
bin[0]=1;
for(int i=1;i<=n;i++)
{
hs[i]=hs[i-1]*p+s[i]-'a'+1;
bin[i]=bin[i-1]*p;
}
}
int getsub(int l,int r)
{
return hs[r]-hs[l-1]*bin[r-l+1];
}
signed main()
{
cin>>s;
s=' '+s;
n=s.size()-1;
shash();
fer(i,1,n/2)
{
if(getsub(1,i)==getsub(n-i+1,n))
{
ans[i]=ans[i-1]+1;
}
else ans[i]=ans[i-1];
}
int m;
cin>>m;
while(m--)
{
int tar;
input(tar);
tar=min(tar-1,n-tar);
cout<<ans[tar]<<'\n';
}
}
G. Shinyruo and KFC
题意为给我们n种，每种个球
问当把这些球分给k个人时有几种分法，每个人每种只能分最多一个
让我们输出
首先如果球比人多肯定是0，因为肯定有人分到超过一个
剩下的对于每个k，答案等于
但这样直接暴力复杂度是
爆了
但注意题种
ai虽然在1e5，但总和不超过1e5，所以他的种类最多有种
所以我们可以用map对组合数去重，重复的直接快速幂乘上去即可
代码如下
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
#define double long double
using namespace std;
template <typename _Tp>void input(_Tp &x){
char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N = 1e6+10;
const int mod=998244353;
int qpow(int a,int b){
int p=mod;
int res=1%p;
while(b){
if(b&1) res=res*1ll*a%p;
a=a*1ll*a%p;
b>>=1;
}
return res;
}
int mul(int a,int b){
return (a*b)%mod;
}
int fc[N],gc[N];
inline void init(){
fc[0]=1;
for(int i=1;i<=500001;i++) fc[i]=mul(fc[i-1],i);
gc[500001]=qpow(fc[500001],mod-2);
for(int i=500001;i>=1;i--) gc[i-1]=mul(gc[i],i);
}
inline int C(int i,int j){
if(j>i)return 0;
return mul(mul(fc[i],gc[j]),gc[i-j]);
}//大组合数
map<int,int> mp;
signed main(){
int n,m;
init();
cin>>n>>m;
int mx=0;
int xx;
fer(i,1,n){
input(xx);
mx=max(mx,xx);
mp[xx]++;
}
fer(i,1,m){
if(i<mx){
cout<<0<<"\n";
continue;
}
else{
int res=1;
for(auto t:mp){
res=mul(res,qpow(C(i,t.first),t.second));
res%=mod;
}
cout<<res<<"\n";
}
}
}
J. Circular Billiard Table
从圆盘的边缘以某个角度发射一颗小球，小球在圆盘内部反弹运动，问第一次回到原点之前一共碰撞了多少次
由反射定律可知小球每两次反射之间的圆心角是相同的，不妨设为 α。
若小球反射 n 次后回到原点，则 nα = k · 360°（k 为某个自然数）。
也就是说，最小的 n 即为最小的 n 使得 360/nα等于一个整数，利用 gcd 算一下即可。
signed main()
{
int T;
cin>>T;
while(T--){
int a,b;
cin>>a>>b;
int c=180*b;
cout<<c/__gcd(c,a)-1<<endl;
}
}
本文含有隐藏内容，请 开通VIP 后查看