Fork me on GitHub

普及五联测D4

版权原因,题面不公开.

刷题王者

思路

直接开$map$统计即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int n;
bool mp[10005];
int main ( void ) {
scanf ( "%d" , &n );
for ( int i = 1 ; i <= n ; i++ ) {
int num;
scanf ( "%d" , &num );
while ( num-- ) {
int x;
scanf ( "%d" , &x );
mp[x] = 1;
}
}
int ans = 0;
for ( int i = 1000 ; i <= 9999 ; i++ )
if ( mp[i] )
ans++;
printf ( "%d\n" , ans );
return 0;
}

回到原点

思路

考虑我们按照原来的字符串进行移动之后的位置$(x,y)$.发现对原来字符串进行操作的话,如果我们把某个向上的和向下的操作变成向左或向右的,那么每次可以从$(x,y)$向左上/下,右上/下移动.
所以我们每次可以对于$x$和$y$的绝对值$+1$或者$-1$.所以答案就是$min(abs(x),abs(y)) + max ( abs ( x ) - min ( abs ( x ) , abs ( y ) ) , abs ( y ) - min ( abs ( x ) , abs ( y ) ) ) / 2$.

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int len , x , y;
char s[N];

int main ( void ) {
scanf ( "%s" , s + 1 );
len = strlen ( s + 1 );
if ( len & 1 ) {
puts ( "-1" );
return 0;
}
for ( int i = 1 ; i <= len ; i++ ) {
if ( s[i] == 'U' )
y++;
if ( s[i] == 'D' )
y--;
if ( s[i] == 'L' )
x--;
if ( s[i] == 'R' )
x++;
}
int ans = 0;
ans += min ( abs ( x ) , abs ( y ) );
if ( x >= 0 )
x -= ans;
else if ( x < 0 )
x += ans;
if ( y >= 0 )
y -= ans;
else if ( y < 0 )
y += ans;
if ( x != 0 )
ans += abs ( x / 2 );
else if ( y != 0 )
ans += abs ( y / 2 );
printf ( "%d\n" , ans );
return 0;
}

快乐矩阵

思路

发现原来某些点的贡献可以压缩到一个点,所以我们对每一行求一个前缀差,然后再对这最后一列的前缀差求一个前缀差,判断一下是否为$0$即可.

代码

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mp[505][505];
int n , m;
int num[505];
signed main ( void ) {
// freopen ( "C.in" , "r" , stdin );
ios :: sync_with_stdio ( false );
cin.tie ( 0 ) , cout.tie ( 0 );
cin >> n >> m;
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= m ; j++ )
cin >> mp[i][j];
for ( int i = 1 ; i <= n ; i++ ) {
int sum = 0;
for ( int j = 1 ; j < m ; j++ )
mp[i][j + 1] -= mp[i][j];
num[i] = mp[i][m];
// cout << num[i] << endl;
}
int now = 0;
for ( int i = 1 ; i < n ; i++ )
num[i + 1] -= num[i];
now = num[n];
if ( abs ( now ) == 0 )
puts ( "Yes" );
else
puts ( "No" );
return 0;
}

梦中的位运算

思路

发现进行操作一定比不操作更优秀,所以我们要求的就是操作到不能再操作了的时候这个序列的平方和.
又因为这个操作的本质就是把$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
#include <bits/stdc++.h>
using namespace std;

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
inline void print ( __int128 x ) {
if ( !x )
return ;
print ( x / 10 );
putchar ( x % 10 + '0' );
return;
}

int n;
int num[35];
__int128 ans;

int main ( void ) {
n = read ();
for ( int i = 1 ; i <= n ; i++ ) {
int x = read ();
for ( int j = 0 ; j <= 30 ; j++ )
if ( x & ( 1 << j ) )
num[j]++;
}
for ( int i = 1 ; i <= n ; i++ ) {
__int128 re = 0;
for ( int j = 0 ; j <= 30 ; j++ )
if ( num[j] >= i )
re |= (1ll << j);
ans += re * re;
}
print ( ans );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:普及五联测D4

文章作者:KRrrrrrrrr

发布时间:2019年10月26日 - 08:10

最后更新:2019年11月05日 - 09:11

原始链接:http://krrrr.xyz/2019/10/26/普及五联测D4/

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