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

0%

第二次周训练

发表于 更新于 Valine：

题目链接

Gym100952

A

思路

很水的题，排个序就好

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
struct node
{
	ll h,m,s;
	bool operator < (const node a)
	{
		if(h!=a.h)return h<a.h;
		else if(m!=a.m)return m<a.m;
		else return s<a.s;
	}
	bool operator == (const node a)
	{
		return a.h==h&&a.m==m&&a.s==s;
	}
}p1,p2; 
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%lld %lld %lld %lld %lld %lld",&p1.h,&p1.m,&p1.s,&p2.h,&p2.m,&p2.s);
		if(p1==p2)printf("Tie\n");
		else if(p1<p2)printf("Player1\n");
		else printf("Player2\n");
	}
}

B

思路

线处理前缀和，然后用upper_bound求出范围，然后再做一下除法就好了

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll pre[35];
ll pow_[35];
void init()
{
	for(int i=0;i<=30;i++)pow_[i]=(1<<i);
	for(int i=1;i<=30;i++)pre[i]=pre[i-1]+pow_[i];
}
int main()
{
	int t;
	scanf("%d ",&t);
	init();
	while(t--)
	{
		int n,m;
		scanf("%d %d",&n,&m);
		int pos = upper_bound(pow_,pow_+30,m)-pow_;
		ll now = 0;
		int ans = 0;
		bool ok = false;
		for(int i=0;i<=pos-1;i++)
		{
			now+=pow_[i];
			ans=i+1;
			if(now>=n)
			{
				ok=true;
				break;
			}
		}
		if(!ok)
		{
			ans+=ceil(1.0*(n-now)/m);
		}
		printf("%d\n",ans);
	}
 }

C

思路

很显然，我们把字符串变成回文串的贡献是一定的，先把回文串的贡献算出来然后我们再考虑应该如何走。
我们把区间分为两部分，左和右，然后只需要变一半的部分就好。
需要分成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
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
//#include<regex>
#include<cstdio>
#include<string>
#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;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
int read()
{
	char ch = getchar(); int 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
int T;
int n,p;
string s; string s1;
int main()
{
	T = read();
	while (T--)
	{
		n = read(); p = read();
		s = " ";
		cin >> s1;
		s += s1;
		int mid = n / 2;
		bool flag = true;
		dwd(i, mid, 1)
		{
			if(s[i]!=s[n-i+1])
			{
				flag = false; break;
			}
		}
		if (flag)cout << 0 << endl;
		else
		{
			int ans = 0;
			int lf = mid+1; int rt = 0;
			dwd(i, mid, 1)
			{
				if (s[i] != s[n - i + 1])
				{
					ans += min(abs(s[i] - s[n - i + 1]), 26 - abs(s[i] - s[n - i + 1]));
					lf = min(lf, i);
					rt = max(rt, i);
				}
			} 
			if (n % 2)if (p == mid + 1)
			{
				cout << ans + p - lf<<endl;
				continue;
			}
			if (n % 2 == 0)if (p == mid) { cout << ans + p-lf<< endl; continue; }
			if (p > mid)p = n - p+1;
			if (p <= lf) { cout << ans + rt  - p << endl; continue; }
			if (p >= rt) { cout << ans + p-lf << endl; continue; }
			int tempans = 1e9;
			tempans = min(n - p + lf, tempans);
			tempans = min(rt - p + rt - lf,tempans);
			tempans = min(tempans, p - lf + rt - lf);
			tempans = min(tempans, p + n - rt);
			cout << tempans + ans << endl;
		}
	}
	return 0;
}

D

思路

用组合数，首先从大于d的数种取k个，取k+1,k+2,,.然后再从不大于d的中选剩下的即可

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e2+10;
const int md = 1e9+7;
ll c[maxn][maxn];
int n,m,k,d;
void init()
{
	for(int i=0;i<maxn;i++)c[i][0]=1,c[i][1]=i;
	for(int i=1;i<maxn;i++)
	{
		for(int j=1;j<=i;j++)
		{
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%md;
		}
	}
}
int main()
{
	init();
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d %d %d",&n,&m,&k,&d);
		int num = 0;
		for(int i=0;i<n;i++)
		{
			int x;
			scanf("%d",&x);
			if(x>=d)num++;
		}
		ll ans = 0;
		int minn = min(num,m);
		for(int i=k;i<=minn;i++)
		{
			ans=(ans+1ll*c[num][i]*c[n-num][m-i])%md;
		}
		printf("%lld\n",ans);
	} 
}

F

思路

先用mp标记标号，然后再把在一起踢过球的团中连边，然后再从Ahmad这个点开始做BFS并且用vis标记，这样就能做到分层了

代码实现

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
//#include<regex>
#include<cstdio>
#include<string>
using namespace std;
#define ll long long
map<string,int>mp;
map<int,string>ma;
int grp[305][305];
bool vis[300];
int maxc,cnt;
struct node
{
	int val;
	int num;
	node(){}
	node(int val,int num):val(val),num(num){}
};
struct Node
{
	string name;
	int val;
	Node(){}
	Node(string name,int val):name(name),val(val){}
	bool operator < (const Node a)
	{
	    if(val!=a.val)return val<a.val;
	    else return name<a.name;
	}
};
vector<Node>ans;
void bfs(int u,int f)
{   
  queue<node>p;
  p.push(node(u,f));
  while(!p.empty())
  {
  	node s = p.front();p.pop();
  	if(vis[s.val])continue;
  	vis[s.val]=true;
  	ans.push_back(Node(ma[s.val],s.num));
  	for(int i=0;i<cnt;i++)
  	{
  		if(i==s.val||!grp[s.val][i])continue;
  		p.push(node(i,s.num+1));
	}
  }
}
int main()
{
	int t;
	scanf("%d",&t);
	int ha=-1;
	while(t--)
	{   maxc = 0;
	    memset(vis,0,sizeof(vis));
	    memset(grp,0,sizeof(grp));
	    ma.clear();
	    mp.clear();
	    ans.clear();
		int n;
		scanf("%d",&n);
		cnt=1;
		for(int i=0;i<n;i++)
		{
			string a,b,c;
			cin>>a>>b>>c;
			if(!mp[a])
			{mp[a]=cnt++,ma[cnt-1]=a;} 
			if(a=="Ahmad"&&ha==-1)ha=cnt-1;
			if(!mp[b]) 
			{mp[b]=cnt++;ma[cnt-1]=b;}
			if(b=="Ahmad"&&ha==-1)ha=cnt-1;
			if(!mp[c]) 
			{mp[c]=cnt++;ma[cnt-1]=c;}
			if(c=="Ahmad"&&ha==-1)ha=cnt-1;
			grp[mp[a]][mp[b]]=grp[mp[b]][mp[a]]=1;
			grp[mp[a]][mp[c]]=grp[mp[c]][mp[a]]=1;
			grp[mp[b]][mp[c]]=grp[mp[c]][mp[b]]=1;
		}
		bfs(ha,0);
		for(int i=1;i<cnt;i++) 
		{
			if(!vis[i])
			{
				ans.push_back(Node(ma[i],10000));
			}
		}
		sort(ans.begin(),ans.end());
		printf("%d\n",cnt-1);
		for(int i=0;i<ans.size();i++)
		{   if(ans[i].val!=10000)
			cout<<ans[i].name<<" "<<ans[i].val<<endl;
			else cout<<ans[i].name<<" "<<"undefined"<<endl;
		}
	}
}

G

思路

经过打表得出除了1，先手必胜

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
	int t ;
	scanf("%d",&t);
	while(t--)
	{
		int x;
		scanf("%d",&x);
		if(x!=1)printf("Alice\n");
		else printf("Bob\n");
	}
}
你最愿意做的哪件事，才是你的天赋所在
-------------你最愿意做的哪件事才是你的天赋所在-------------