# Primality Test

根据题意可知,求连续两个质数相加除以 2 向下取整后是否还是质数,因为是连续的两个质数,所以取中位数后一定不会是质数,1 除外

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL t , n;
int main()
{
    scanf("%lld" , &t);
    while (t --)
    {
        scanf("%lld" , &n);
        if (n == 1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

# Nun Heh Heh Aaaaaaaaaaa

给定一个字符串,求这个字符串有多少个子序列满足由前缀 nunhehheh 和 k 个 a (k>0) 组成。

例如 nunhehhehaaaaaa 就是符合要求的,但是 nunhehheh 和 nunhehhehoooaaa 是不符合要求的。

这是一个 dp 模型,求一个字符串的所有子序列中有多少个 s (s 是一个字符串),这里只是多了后缀 a,我们先找字符串包含多少个 nunhehheh,开一个 dp 数组,dp [i] 表示匹配到匹配到第 k 个字符出现了前 i 个字串的数量,例如 dp [1] 表示出现 n 的数量,dp [3] 表示出现 nun 的数量,遍历字符串,将对应的字符,dp [i]=(dp [i-1]+dp [i])% mod

最后 dp [9] 就是出现 nunhehheh 的数量,用 dp [10] 表示前缀 nunhehheh 和 k 个 a (k>0) 组成的字符串数量,考虑给后面加上一个 a,那么之前满足条件的字符串可以加 a 也可以不加,而 dp [9] 必须加上这个 a 才能满足条件,所以 dp [10]=(dp [10]+dp [9])% mod

#include <bits/stdc++.h>
#define endl '\n'
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
ll mod=998244353;
ll dp[20],T;
int main()
{
	ios;
	cin>>T;
	while(T--){
		memset(dp,0,sizeof dp);
		string s;
		cin>>s;
		int len=s.size();
		for(int i=0;i<len;i++){
			if(s[i]=='n'){
				dp[1]++;
				dp[3]=(dp[3]+dp[2])%mod;
			}
			else if(s[i]=='u') dp[2]=(dp[1]+dp[2])%mod;
			else if(s[i]=='h'){	// 这里需要特别注意如果出现连续相同的字符,例如 aaaa,那需要先更新最后一个 a 的答案,因为这里计算出现多少个 aaaa,如果当前位置是 k,那当前答案是用 [1,k-1] 出现 aaa 的数量来更新的,如果先更新前面的 a,就会导致使用 [1,k] 出现的 a 来更新答案,导致错误
				dp[9]=(dp[9]+dp[8])%mod;
				dp[7]=(dp[7]+dp[6])%mod;
				dp[6]=(dp[6]+dp[5])%mod;
				dp[4]=(dp[4]+dp[3])%mod;
			}
			else if(s[i]=='e'){
				dp[5]=(dp[4]+dp[5])%mod;
				dp[8]=(dp[8]+dp[7])%mod;
			}
			else if(s[i]=='a') dp[10]=(dp[10]*2%mod+dp[9])%mod;
		}
		cout<<dp[10]<<endl;
	}
	return 0;
}

# Kanade Doesn't Want to Learn CG

分类讨论,数学问题,我用小数写的,但是其实用 longlong 更好,不会有精度问题

#include <bits/stdc++.h>
#define endl '\n'
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const ll mod=998244353;
int T;
double a,b,c,x0,y0,x1,y1,y2;
double f1(ll y){
	return (-b+sqrt(b*b-4*a*(c-y0)))/(2*a);
}
double f2(ll y){
	return (-b-sqrt(b*b-4*a*(c-y0)))/(2*a);
}
double work(double x){
	return a*x*x+b*x+c;
}
int main()
{
	ios;
	cin>>T;
	while(T--){
		cin>>a>>b>>c;
		cin>>x0>>x1>>y0>>y1>>y2;
		if(work(x0)==y0 || work(x1)==y0) cout<<"No"<<endl;
		else{
			double p=-b/(2*a);
			if(work(p)<=y0 || p>=x1 || (f1(y0)>=x0 && f1(y0)<=x1)) cout<<"No"<<endl;
			else if(f2(y0)>x0 && f2(y0)<x1) cout<<"Yes"<<endl;
			else{
				if(work(x1)<=y2 && f2(y0)>x1 && f2(y0)<x1+x1-x0) cout<<"Yes"<<endl;
				else cout<<"No"<<endl;
			}
		}
	}
	return 0;
}

更好的代码如下

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll mod = 998244353;
ll a, b, c, xa, xb, ya, yb, yc;
ll changdu(ll x){
    ll res = a * x * x + b * x + c;
    return res;
}
int main() {
    ios;
    int t;
    cin >> t;
    while(t --){
        cin >> a >> b >> c >> xa >> xb >> ya >> yb >> yc;
        ll lena = changdu(xb), lenb = changdu(0 - xa + xb * 2), len = changdu(xa);
        if (len <= ya) cout << "No\n";
        else if (lena == ya || lena > yc) cout << "No\n";
        else if (lena < ya) cout << "Yes\n";
        else{
            if (lenb >= ya) cout << "No\n";
            else cout << "Yes\n";
        }
    }
    return 0;
}

# Jumping Monkey

比赛的时候一直在想从边权大的开始出发,把所有能到达这个点的所有点答案加一,利用线段树去维护,但是到后面块太多了,维护不了,于是就搁置了,正解是从边权小的开始枚举,对于当前点,把和这个点相邻的点都合并到当前点,让当前点作为祖先,循环往复,到最后每一个点距离根节点的距离就是答案,原理就是因为是按照点权从小到大枚举的,因此每一个点都不可能越过根节点到达其他分支的节点,所以一个节点可以到达的节点就是这个点距离和根节点之间的点,也就是距离。

#include <bits/stdc++.h>
#define endl '\n'
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int N=2e5+100;
struct node{
	int id,val;
}arr[N];
int T,n,u,v;
int fa[N],ans[N];
bool vis[N];
vector<int> ve[N];
bool cmp(node a,node b){
	return a.val<b.val;
}
int find(int x){
	if(x==fa[x]) return x;
	else{
		int tmp=fa[x];
		fa[x]=find(fa[x]);
		ans[x]+=ans[tmp];	// 维护距离根节点的距离
		return fa[x];
	}
}
void init(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
		ans[i]=0;
		ve[i].clear();	
		vis[i]=0;
	} 
}
int main()
{
	ios;
	cin>>T;
	while(T--){
		cin>>n;
		init();
		for(int i=1;i<n;i++){
			cin>>u>>v;
			ve[u].push_back(v);
			ve[v].push_back(u);
		}
		for(int i=1;i<=n;i++){
			cin>>arr[i].val;
			arr[i].id=i;
		}
		sort(arr+1,arr+1+n,cmp);
		for(int i=1;i<=n;i++){
			int now=arr[i].id;
			for(int j=0;j<ve[now].size();j++){
				if(vis[ve[now][j]]){
					int fu=find(ve[now][j]);
					ans[fu]=1;
					fa[fu]=now;
				}
			}
			vis[now]=1;
		}
		for(int i=1;i<=n;i++){
			find(i);
			cout<<ans[i]+1<<endl;
		}
	}
	return 0;
}

# Monopoly

a1,a2,a3...ana1,a2,a3...an

首先求一个前缀和,S=Kpre[n]+pre[i]S=K*pre[n]+pre[i],考虑 pre [n] 大于 0 的情况,这个时候 pre [i] 一定小于等于 S,对 pre [n] 取模,发现 S 和 pre [i] 同余,也就是求一个 pre [i] 使得 K 最小,并且在 K 相同条件下 i 尽可能小,考虑维护 n 个容器,每一个容器对应一个余数,容器中放置所有同余的前缀和,给定一个 x 就去相对应的容器中二分找到小于等于 x 的最大前缀,即是答案。

需要特别注意的是,前缀和可能是负数,而给定的 x 是负数,这个时候 x 和前缀和是同余的,但是符号相反,这里需要特别处理一下。

如果 pre [n] 小于 0,则所有数字取反即可。

#include <iostream>
#include <string.h>
#include <map>
#include <algorithm>
#include <vector>
#define endl '\n'
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int N=2e5+100;
typedef long long ll;
int n,m;
ll arr[N];
vector<ll> cis[N];
int tot,T;
map<ll,int> mp,mp2;
void init(){
	mp.clear();
	mp2.clear();
	for(int i=1;i<=tot;i++) cis[i].clear();
	tot=0;
}
int main()
{
	ios;
	cin>>T;
	while(T--){
		init();
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>arr[i];
			arr[i]+=arr[i-1];
		}
		ll sum=arr[n];
		int flag=0;
		if(sum<0){
			for(int i=1;i<=n;i++) arr[i]=-arr[i];
			sum=-sum;
			flag=1;
		}
		for(int i=1;i<=n;i++) if(!mp2[arr[i]]) mp2[arr[i]]=i;;
		if(sum!=0){
			for(int i=1;i<=n;i++){
				ll now=(arr[i]%sum+sum)%sum;
				if(!mp[now]) mp[now]=++tot;
				cis[mp[now]].push_back(arr[i]);
			}
		}
		for(int i=1;i<=tot;i++) sort(cis[i].begin(),cis[i].end());
		while(m--){
			ll x;
			cin>>x;
			if(flag) x=-x;
			if(x==0){
				cout<<0<<endl;
				continue;
			}
			if(sum==0){
				if(mp2[x]) cout<<mp2[x]<<endl;
				else cout<<-1<<endl;
				continue;
			}
			if(!mp[(x%sum+sum)%sum]){
				cout<<-1<<endl;
				continue;
			}
			int now=mp[(x%sum+sum)%sum];
			auto it=upper_bound(cis[now].begin(),cis[now].end(),x);
			if(it==cis[now].begin()) cout<<-1<<endl;
			else{
				it--;
				cout<<(x-*it)/sum*n+mp2[*it]<<endl;
			}
		}
	}
	return 0;
}
/*
1
4 4
1 2 -3 3
1
3
6
7
*/
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝