你最愿意做的哪件事，才是你的天赋所在

0%

Educational Codeforces Round 85

发表于 更新于 Valine：

题目连接

Educational Codeforces Round 85
赛后20分钟A题被hacked了，我没得心态了

A

思路

就是根据题意来，一共有四种情况(写的时候少了一种，竟然还给过了，于是就被hacked)，判断一下就可以了

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e2+10;
int a[N];
int b[N];
int main(){
	int t;
	scanf("%d",&t); 
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++)scanf("%d %d",&a[i],&b[i]);
		bool flag = 0;
		if(b[0]>a[0]){
			printf("NO\n");
			continue;
		}
		for(int i=1;i<n;i++){
			if((b[i]-b[i-1]>a[i]-a[i-1])||a[i]<a[i-1]||b[i]>a[i]||b[i]<b[i-1]||(b[i]>b[i-1]&&a[i]==a[i-1])){
				flag=1;
				printf("NO\n");
				break;
			}
		}
		if(!flag)printf("YES\n");
	}
}

B

代码实现

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
	char ch = getchar(); ll x = 0, f = 1;
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e5 + 10;
int T, n, x;
ll a[N];
int main()
{
	T = read();
	while (T--)
	{
		n = read(), x = read();
		upd(i, 1, n)a[i] = read();
		ll sum = 0;
		upd(i, 1, n)
		{
			sum += a[i];
		}
		ll temp = 1ll * x * n;
		sort(a + 1, a + n + 1);
		int nn = n;
		int cnt = 1;
		while (nn)
		{
			if (sum >= temp)
			{
				break;
			}
			sum -= a[cnt];
			cnt++;
			nn--;
			temp = 1ll * x*nn;
		}
		printf("%d\n", nn);
	}
	return 0;
}

C

思路

先处理一遍b数组，伤害等于min(b[i],a[i+1])，然后找到最小的b，从那个地方开始射击就是最小值

代码实现

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>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 3e5+10;
ll a[N];
ll b[N];
int main(){
   int t;
   scanf("%d",&t);
   while(t--){
   	   int n;
   	   scanf("%d",&n);
   	   ll suma=0,sumb=0;
   	   for(int i=0;i<n;i++){
   	   	 scanf("%lld %lld",&a[i],&b[i]);
   	   	 suma+=a[i];
		}
		b[n-1]=min(b[n-1],a[0]);
		for(int i=0;i<n-1;i++)b[i]=min(b[i],a[i+1]);
		ll minn = 1e18+10;
		for(int i=0;i<n;i++){sumb+=b[i];minn=min(minn,b[i]);}
		printf("%lld\n",suma-sumb+minn);
   }	
}

D

思路

很好发现规律就是121314151~n 232425262~n 343536~n，然后模拟即可

代码实现

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
	char ch = getchar(); ll x = 0, f = 1;
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e5 + 10;
int T, n;
ll l, r;
int a[N];
vector<int>vec1;
int main()
{
	T = read();
	while (T--)
	{
		n = read();
		l = read(), r = read();
		ll sum = 0;
		int pos_l = 0;
		int pos_r = 0;
		ll temp_l;
		ll l_sum;
		upd(i, 1, n)
		{
			ll tempsum = 2ll * (n - i) + sum;
			if (i == n)tempsum++;
			if (l <= tempsum && l >= sum)
			{
				temp_l = 2ll * (n - i);
				l_sum = sum;
				pos_l = i;
				break;
			}
			sum += 2 * (n - i);
		}
		sum = 0;
		ll temp_r;
		ll r_sum;
		upd(i, 1, n)
		{
			ll tempsum = 2ll * (n - i) + sum;
			if (i == n)tempsum++;
			if (r <= tempsum && r >= sum)
			{
				temp_r = 2ll * (n - i);
				r_sum = sum;
				pos_r = i;
				break;
			}
			sum += 2ll * (n - i);
		}
		if (pos_l == pos_r)
		{
			if (pos_l == n)printf("%d\n", 1);
			else {
				l -= l_sum;
				r -= r_sum;
				upd(j, l, r)
				{
					if (j % 2 == 0)
						printf("%d ", pos_l + (j / 2));
					else printf("%d ", pos_r);
				}
			}
			continue;
		}
		l -= l_sum;
		upd(j, l, temp_l)
		{
			if (j % 2 == 0)
				printf("%d ", pos_l + (j / 2));
			else printf("%d ", pos_l);
		}
		upd(i, pos_l + 1, pos_r - 1)
		{
			int block = 2 * (n - i);
			upd(j, 1, block)
			{
				if (j % 2 == 0)
					printf("%d ", i + (j / 2));
				else printf("%d ", i);
			}
		}
		r -= r_sum;
		if (pos_r == n)printf("%d ", 1);
		else {
			upd(j, 1, r)
			{
				if (j % 2 == 0)
					printf("%d ", pos_r + (j / 2));
				else printf("%d ", pos_r);
			}
		}
		printf("\n");
	}
	return 0;
}

E

思路

先理解题意，就是把D的质因子一个个拆出来组成图，2个数a,b之间的最短路径=gcd(a,b)到a的最短路乘上gcd(a,b)到b的最短路，脑袋中想象一下gcd(a,b)就相当于a，b的交通枢纽。然后需要分解质因子，由于查询的都是D的因子，所以我们只需要把D的质因数存起来用来后面分解就可以了。然后如何统计答案？例如从2~223*3的答案很显然就是2 3 3的全排列，就是多出来的一部分的全排列再除以相同的部分，也就是部分排列，统计两部分后相乘即可，如果直接使用逆元会炸，预处理一波即可

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 998244353;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
vector<int>fac;
vector<int>ifac;
ll prime[500],cnt;
const int N = 100;
ll pp[N];
ll in[N];
int main(){
	ll d;
	scanf("%lld",&d);
	pp[0]=1;
	for(int i=1;i<N;i++)pp[i]=1ll*pp[i-1]*i%mod;
	for(int i=1;i<N;i++)in[i]=inv(pp[i]);
	ll temp=d;
	for(int i=2;1ll*i*i<=d;i++){
		if(d%i==0){
			while(d%i==0){
				d/=i;
			}
			prime[cnt++]=i;
		}
	}
	if(d!=1)prime[cnt++]=d;
	int q;
	scanf("%d",&q);
	while(q--){
		ll x,y;
		fac.clear();
		ifac.clear();
		scanf("%lld %lld",&x,&y);
		if(x<y)swap(x,y);
		int sum = 0;
		int sum1 = 0;
		//分解x与y 
		for(int i=0;i<cnt;i++){
			int p = 0;
			if(x%prime[i]==0||y%prime[i]==0){
				while(x%prime[i]==0){
			    p++;
				x/=prime[i];
				}
				while(y%prime[i]==0){
					p--;
					y/=prime[i];
				}
				if(p>0){
				fac.push_back(p);
				sum+=p;
			    }
			    else if(p<0){
			    	ifac.push_back(-p);
			    	sum1-=p;
				}
			}
		}
		ll fz=pp[sum];
		ll fm=pp[sum1];
		for(auto k : ifac){
			fm=fm*in[k]%mod;
		}
		for(auto k:fac){
			fz=fz*in[k]%mod;
		}
		ll ans = fz*fm%mod;
		printf("%lld\n",ans);
	}
}
-------------你最愿意做的哪件事才是你的天赋所在-------------