Codeforces Round #739

A:水题,预处理一下符合题目要求的数即可。

Codeforces Round #739

 

 

 

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include<queue>
 5 #include<unordered_map>
 6 using namespace std;
 7 const int N=1010;
 8 int q[N];
 9 int main()
10 {
11     int i=1;
12     int cnt=1;
13     while(cnt<=1004){
14         if(i%3==0||i%10==3){
15             i++;
16             continue;
17         }
18         q[cnt++]=i;
19         i++;
20     }
21     int t;
22     cin>>t;
23     while(t--){
24         int k;
25         cin>>k;
26         cout<<q[k]<<endl;
27     }
28     return 0;
29 }

 

B:从1~n(n为偶数),n个人围圈坐,给定a和b相对,问c和谁相对。

abs(a-b)即为n/2,然后(c+n/2)%n即为答案。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include<queue>
 5 #include<unordered_map>
 6 using namespace std;
 7 int main()
 8 {
 9     int t;
10     cin>>t;
11     while(t--){
12         int a,b,c;
13         cin>>a>>b>>c;
14         int n_2=abs(a-b);
15         int n=n_2*2;
16         if(a>n||b>n||c>n)
17             cout<<-1<<endl;
18         else{
19             int res=c+n_2;
20             if(res>n)
21                 cout<<res-n<<endl;
22             else
23                 cout<<res<<endl;
24         }
25     }
26     return 0;
27 }

 

C:给定一个如此排布的棋盘,问给定x在多少行多少列。

Codeforces Round #739

 

 这个问题非常不好考虑,但是顺着来就较为简单了。

也就是给定行列,问你这个数是多少。

当r<=c时,x=(c-1)*(c-1) + r

当r>=c时,x=r*r - c + 1

 然后我们可以根据方程逆推出r和c(试出来)

也就是计算r和c,然后判断条件是否符合。

 1 #include <iostream>
 2 #include<cmath>
 3 using namespace std;
 4 typedef long long LL;
 5 int main()
 6 {
 7     int T;
 8     cin>>T;
 9     while(T--){
10         LL k;
11         cin>>k;
12         if(k==1){
13             cout<<1<<" "<<1<<endl;
14             continue;
15         }
16         LL t=sqrt(k);
17         LL c1=t + 1;
18         LL r1=k - (c1-1)*(c1-1);
19         if(r1<0||((c1-1)*(c1-1)+r1>k)){
20             c1=t;
21             r1=k - (c1-1)*(c1-1);
22         }
23         if(r1>0&&c1>0&&r1<=c1){
24             cout<<r1<<" "<<c1<<endl;
25             continue;
26         }
27         LL r2=t;
28         LL c2=r2*r2-k+1;
29         if(c2<0||(r2*r2-c2+1<k)){
30             r2=t+1;
31             c2=r2*r2-k+1;
32         }
33         cout<<r2<<" "<<c2<<endl;
34     }
35     return 0;
36 }

 

D:给定一个整数,问最少多少步能够将其变成2的次方。

每一步有两种操作,一是删除一个数,二是在尾部添加一个数。

根据每一步可以做的操作可以发现,假设给定一个2的次方(比如1024),和一个数x。

关键的是x与1024从头开始的匹配个数(注意是x的子序列匹配1024)。

答案即len(x) - x中匹配了的 + len(1024) - 1024中没匹配的

再看有每次1e4个测试数据,而2^(60)=1e18。

计算次数最多为1e4*60,故可行。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include<queue>
 5 #include<unordered_map>
 6 #include<cmath>
 7 using namespace std;
 8 typedef long long LL;
 9 const int N=60;
10 string s[N];
11 void fun(){
12     LL a=1;
13     for(int i=0;i<=60;i++){
14         s[i]=to_string(a);
15         a=a*2;
16     }
17 }
18 int finds(string t,int i){
19     string tar=s[i];
20     int n1=tar.size();
21     int n2=t.size();
22     int res=0x3f3f3f3f;
23     int now=0;//now表示待匹配的
24     for(int i=0;i<t.size();i++){
25         if(now<n1&&t[i]==tar[now]){
26             now++;
27         }
28         res=min(res,n2-(now)+n1-(now));
29     }
30     return res;
31 }
32 int main()
33 {
34     fun();
35     int t;
36     cin>>t;
37     while(t--){
38         LL n;
39         cin>>n;
40         string t=to_string(n);
41         int res=0x3f3f3f3f;
42         for(int i=0;i<=60;i++){
43             res=min(res,finds(t,i));
44         }
45         cout<<res<<endl;
46     }
47     return 0;
48 }

 

后面的没做。。。

Codeforces Round #739

上一篇:Vue component 父子组件通信 props


下一篇:2021-8-20 Make a Power of Two