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

0%

11-9训练赛

发表于 Valine：

Palindromes

题目链接

Palindromes

思路

要求就是求第k大的回文数，k很大，我们考虑二分。
首先二分出位数，然后减去后再减去一，然后把第一位加上1再反转过来就是答案。细节很多，值得注意。

代码实现

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h> 
using namespace std;
#define ll long long
string dezero(string a)//用来去掉正数前面的0，也就是说可以输入000001类似这样的数字
{
	long int i;
	for(i=0;i<a.length();i++)
	{
		if(a.at(i)>48) break;
	}
	if(i==a.length()) return "0";
	a.erase(0,i);
	return a;
}
int judge(string a,string b)//判断两个正数的大小
{
	if(a.length()>b.length()) return 1;
	if(a.length()<b.length()) return -1;
	long int i;
	for(i=0;i<a.length();i++)
	{
		if(a.at(i)>b.at(i)) return 1;
		if(a.at(i)<b.at(i)) return -1;
	}
	return 0;
}
string sub(string a,string b)//自然数减法
{
	a=dezero(a);
	b=dezero(b);
	long int i,j=0;
	string c="0";
	string c1,c2;
	string d="-";
	if(judge(a,b)==0) return c;
	if(judge(a,b)==1)
	{
		c1=a;
		c2=b;
	}
	if(judge(a,b)==-1)
	{
		c1=b;
		c2=a;
		j=-1;
	}
	reverse(c1.begin(),c1.end());
	reverse(c2.begin(),c2.end());
	for(i=0;i<c2.length();i++)
	{
		if(c2.at(i)>=48&&c2.at(i)<=57) c2.at(i)-=48;
		if(c2.at(i)>=97&&c2.at(i)<=122) c2.at(i)-=87;
	}
	for(i=0;i<c1.length();i++)
	{
		if(c1.at(i)>=48&&c1.at(i)<=57) c1.at(i)-=48;
		if(c1.at(i)>=97&&c1.at(i)<=122) c1.at(i)-=87;
	}
	for(i=0;i<c2.length();i++)
	{
		c1.at(i)=c1.at(i)-c2.at(i);
	}
	for(i=0;i<c1.length()-1;i++)
	{
		if(c1.at(i)<0)
		{
			c1.at(i)+=10;
			c1.at(i+1)--;
		}
	}
	for(i=c1.length()-1;i>=0;i--)
	{
		if(c1.at(i)>0) break;
	}
	c1.erase(i+1,c1.length());
	for(i=0;i<c1.length();i++)
	{
		if(c1.at(i)>=10) c1.at(i)+=87;
		if(c1.at(i)<10) c1.at(i)+=48;
	}
	reverse(c1.begin(),c1.end());
	if(j==-1) c1.insert(0,d);
	return c1;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string k;
		cin>>k;
		if(judge(k,"1")==0)
		{
			cout<<"0"<<endl;
			continue;
		}
		int l=0,r=10000000;
		int ans=0;
		while(l<r-1)
		{
			string s;
			int mid = (l+r)>>1;
			s=string((mid+1)/2+1,'9');
			if(mid%2==1)
			{
				s[1]='0';
			}
			s[0]='1';
			if(mid==0)s="0";
			if(judge(k,s)==1)l=mid;
			else r=mid;
		}
		ans=l;
		string s=string((ans+1)/2+1,'9');
		if(ans%2==1)
		{
				s[1]='0';
		}
		s[0]='1';
		k=sub(k,s);
		k=sub(k,"1");
		int tans =ans+1;
		ans=(ans+2)/2;
		while(k.size()<ans)
		{
			k.insert(k.begin(),'0');
		}
		k[0]+=1;
		string k1 = k;
		reverse(k.begin(),k.end());
		ans++;
		if(tans<=1)
		{
			cout<<k<<endl;
			continue;
		}
		if(tans%2==0)k1+=k;
		else 
		{
			k.erase(k.begin());
			k1+=k;
		}
		cout<<k1<<endl;
	}
}

Frog and Portal

题目链接

Frog and Protal

思路

因为M范围在2的32次方内，所以大概在50位就超过了。
因为前面回影响到后面，我们考虑拆分斐波那契数列，把它拆成一个个相加。然后我们控制前面奇数位置上放通道的起点，偶数位置上不放，这样就能保证想进入通道就只有一种方法，然后通道通向后面的200-i，i就是我们找到的位置，因为后面的位置之间不会有影响，所以直接加起来就好。最后记得建一堵墙。

代码实现

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 
vector<int>pos;
ll f[205];
int main()
{
	f[1]=1;
	f[2]=1;
	for(int i=3;i<=55;i++)f[i]=f[i-1]+f[i-2];
	for(int i=0;i<=55;i++)f[i]=f[i+1];
	f[0]=0;
	ll m;
	while(cin>>m)
	{
	pos.clear();
	if(m==0)
	{
		printf("2\n1 1\n2 1\n");
		continue;
	}
	while(m)
	{
		int num = upper_bound(f,f+52,m)-f;
			 pos.push_back(num-1);
			 m-=f[num-1];
	}
	printf("%d\n",pos.size()+1);
	//sort(pos.begin(),pos.end());
	int cnt = 1;
	for(int i=0;i<pos.size();i++)
	{
		printf("%d %d\n",cnt,200-pos[i]);
		cnt+=2;
	}
	printf("%d %d\n",cnt-1,cnt-1);
   }
}
-------------你最愿意做的哪件事才是你的天赋所在-------------