Fork me on GitHub

Round

qwq


A:
这道题能想到二进制转十进制然后判断满足的个数,
但是转十进制范围已经超过了$long long$,直接模拟会溢出
因为满足条件数值的都是4的次幂,所以二进制首位1后跟的$2k$个$0$即为$4$的$k$次幂
直接对$0$的个数分析即可


B:
很明显的一道贪心题目,当求最小的$sum$时,显然当$1$最多时,$sum$最小.当求$sum$最大时同理.又因为当$a_i$是一个偶数时,$\frac{a_i}{2}$肯定存在,而且$a_i$的最小值为1,所以显然$a_i$的值就只能是$2^j$.


C:
(个人感觉比$D$难$QAQ…$)
让你在给定的序列$P$中求一个子序列,使得在图中按照该子序列进行最短路径移动时可以完整经过原序列$P$.
乍一看一点思路都没有.但是仔细思考可以发现一点点思路.我们可以从题目中给出的起点(也就是一号点)开始进行移动,然后在原序列$P$中如果需要经过$P_{i}$和$P_{i+1}$,那么我们显然可以得到$P_i$与$P_{i+1}$一定是直接相连的(因为题目中没有给出无解的情况).那么我们可以扩展一下,假设我们现在在$P_j$号点,我们要走到$P_k$号点.那么如果$dis[P_j][P_k]==j-k$,那么在有解的情况下,一定是有$P_j$经过了所有的$j<i<k$的点(可以自己画个图证明一下).在这种情况下,我们就可以选择扩展答案了.

(感觉还是放一下代码比较好qwq)

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
#include<bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const int N = 105;
const int M = 1e6 + 10;
int n,m,idx;
char mp[N][N];
int G[N][N],point[M],ans[M];
int qu[M<<1];
int head=1,tai=0;
int main(){
memset ( G , 0x3f3f3f3f , sizeof ( G ) );
scanf ( "%d" , &n );
for ( int i = 1 ; i <= n ; i++ )
scanf ( "%s" , mp[i] + 1 );
for ( int i = 1 ; i <= n ; i++ ) {
for ( int j = 1 ; j <= n ; j++ )
if ( mp[i][j] == '1' )
G[i][j] = 1;
G[i][i] = 1;
}
for ( int k = 1 ; k <= n ; k++ )
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= n ; j++ )
G[i][j] = min ( G[i][j] , G[i][k] + G[k][j] );
scanf("%d",&m);
for ( int i = 1 ; i <= m ; i++ )
scanf ( "%d" , &point[i] );
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)
// printf("%d " ,G[i][j]);
// puts("");
// }
int st=1,now=2;
while(now<=m){
int diss=now-st;
if(diss==G[point[st]][point[now]]){
if(head<=tai)
head++;
qu[++tai]=now;
now++;
}
else {
ans[++idx]=point[st];
if(head<=tai)
st=qu[head++];
}
}
ans[++idx]=point[st];
if(ans[idx]!=point[m])
ans[++idx]=point[m];
printf("%d\n",idx);
for(int i=1;i<=idx;i++)
printf ("%d ",ans[i]);
return 0;
}

D:
感觉比$C$简单啊$QAQ$….
让你求一个字符串使得这个字符串和给定01字符串的每一个子区间的最长单调不降区间长度一样长.
我们自己理解了以后可以发现,一个区间的最长单调不降区间长度只是和每一个$1$后的$0$有关系,而和$0$后的$1$无关.(因为对于两个子串$11$和$01$,它们的最长不降区间是一样的).那么我们就可以考虑把原字符串的一些$1$变成$0$.就可以了.

但是怎么改变呢?我们考虑到,对于某一段连续的$1$,那么这段连续区间中的第一个1很显然是不必要的(而且不是最后一个1),那么我们可以把这些个1变成0.(然后就做完辣qwq)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int tmpp;
char ss[N] , tt[N];
int main(){
scanf ( "%s" , ss + 1 );
int len = strlen ( ss + 1 );
for ( int i = 1 ; i <= len ; i++ )
tt[i] = ss[i];
for ( int i = len ; i >= 1 ; i-- ) {
if ( ss[i] == '1' && tmpp >= 0 )
tt[i] = '0';
int cur=ss[i] == '1' ? 1 : -1;
tmpp = min ( tmpp + cur , cur );
}
for ( int i = 1 ; i <= len ; i++ )
printf ( "%c" , tt[i] );
return 0;
}
//

E:
现在还不会qwq

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:Round

文章作者:KRrrrrrrrr

发布时间:2019年09月11日 - 18:09

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.xyz/2019/09/11/Round/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。