Codeforces Round #586 A、B、C三道简单题

凌晨开始也太难顶了八，a完三题都一点半了（B题我傻了卡了一会儿），顶不住了， 就睡了（熬夜伤肝）›´ω`‹ 

586A. Cards

大致题意：

 Serezha三岁生日的时候，收到了一堆卡片，由于他麻麻喜欢二进制，所有只有0和1，现在卡片字母顺序被打乱了，他粑粑想知道可以拼成的最大二进制数是多少。

思路：

我们仔细观察one和zero的特征字母分别是“n”和“z”，所以只要统计“n”和“z”出现的次数，然后按数量先输出1在输出0就ok了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 using std::bitset;
 4 typedef long long ll;
 5 
 6 int main()
 7 {
 8     int len;
 9     while(~scanf("%d",&len))
10     {
11         string p;
12         cin>>p;
13         int z=0,n=0;
14         for(int i=0;i<len;i++)
15         {
16             if(p[i]==‘n‘)
17                 n++;
18             else if(p[i]==‘z‘)
19                 z++;
20         }
21         while(n--)
22             cout<<"1"<<" ";
23         while(z--)
24             cout<<"0"<<" ";
25             cout<<endl;
26     }
27     return 0;
28 }

View Code

586B. Multiplication Table

 题意：

给你一个n*n矩阵M，存在一个数列a_n，满足矩阵M_ij=a_i*a_j，但是主对角线被挖去（给的话直接开方就行了），求出数列a_n。

思路：

一开始我想的是n个方程解n个未知数，后来没解出来。然后我就猜a_i是第i行的最大公约数，结果发现是错的。（太蠢了）

n小于1000，实际上对于整数i∈[2,n-1]，都可以在矩阵中找到M[i-1][i]，M[i][i+1]，M[i-1][i+1]，然后用M[i-1][i]*M[i][i+1]/M[i-1][i+1]可以得到(a_i)²    (这样算可能爆int)

得到a₂~a_n-1后算a₁和a_n就很简单了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 using std::bitset;
 4 typedef long long ll;
 5 
 6 ll b[1005][1005];
 7 ll a[1005];
 8 
 9 int main()
10 {
11     int n;
12     while(~scanf("%d",&n))
13     {
14         memset(a,0,sizeof(a));
15         memset(b,0,sizeof(b));
16         for(int i=1;i<=n;i++)
17             for(int j=1;j<=n;j++)
18             scanf("%d",&b[i][j]);
19         for(int i=2;i<n;i++)
20         {
21             a[i]=sqrt((b[i-1][i]*b[i][i+1])/b[i-1][i+1]);
22         }
23         a[1]=b[1][2]/a[2];
24         a[n]=b[1][n]/a[1];
25         for(int i=1;i<=n;i++)
26             cout<<a[i]<<" ";
27         cout<<endl;
28     }
29     return 0;
30 }

View Code

586C. Substring Game in the Lesson

题意：

Mike and Ann玩一个游戏，有一个长度为n的字符串s和一个数字k，要求从s[k]开始向两边拓展字串，平且操作后得到的子串的字典序要比原来小，不能进行操作的人输。Ann先手，逐次输出每个k=i是的胜者。

思路：

这个博弈比较好想，因为对一个串，往后加字典序一定增大，只有往前加比这个串首字符小的字符，字典序才会减小

所以对于每个s[k]只要存在s[i]<s[k],且i<k则Ann必胜，否则必输，即Mike必胜

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 using std::bitset;
 4 
 5 string ans;
 6 bool k[500005];
 7 
 8 int main()
 9 {
10     while(cin>>ans)
11     {
12         k[0]=false;
13         char minn=ans[0];
14         for(int i=1;i<ans.length();i++)
15         {
16             if(ans[i]>minn)
17                 k[i]=true;
18             else
19                 k[i]=false;
20             if(ans[i]<minn)
21                 minn=ans[i];
22         }
23         for(int i=0;i<ans.length();i++)
24         {
25             if(k[i])
26                 cout<<"Ann"<<endl;
27             else
28                 cout<<"Mike"<<endl;
29         }
30     }
31     return 0;
32 }

View Code

后面的题，题目都没看，先留个坑 ( ‘-ω?? )