Primality Test

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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更好，不会有精度问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}

更好的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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…an$

首先求一个前缀和，$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，则所有数字取反即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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
*/