ZROI普及五连测 \(Day4\)
A.刷题王者
水题,略
B.回到原点
先把能抵消的全部抵消,剩下的就是需要调整的.
剩下的一定是不能抵消的,而且 \(U,D\) 和 \(L,R\) 两组一定是每组至多剩一种没有匹配完.
调整的时候,考虑自身内部调整和相互匹配,取 \(min\) 即可.
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
#define mabs(x) ( x < 0 ? - x : x )
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 1e3 + 10 ;
char s[N] ;
int v[N] , w[N] ;
int n , x , y ;
int cnt[4] ;
signed main (int argc , char * argv[]) {
scanf ("%s" , s + 1 ) ; n = strlen ( s + 1 ) ;
if ( n & 1 ) return puts ("-1") , 0 ;
rep ( i , 1 , n ) if ( s[i] == 'U' ) v[i] = 1 ; else if ( s[i] == 'D' ) v[i] = - 1 ;
rep ( i , 1 , n ) if ( s[i] == 'L' ) w[i] = 1 ; else if ( s[i] == 'R' ) w[i] = - 1 ;
rep ( i , 1 , n ) { v[i] += v[i-1] ; w[i] += w[i-1] ; }
x = abs ( v[n] ) ; y = abs ( w[n] ) ;
if ( ( x + y ) & 1 ) return puts ("-1") , 0 ;
if ( x == y ) printf ("%d\n" , x ) ;
else {
int del = abs ( x - y ) ;
if ( x > y ) x -= del , y += del ;
else x += del , y -= del ;
if ( ( x & 1 ) && ( y & 1 ) ) {
int tmp = x / 2 + y / 2 + 1 ;
printf ("%d\n" , min ( del + x , tmp ) ) ;
} else {
int tmp = x / 2 + y / 2 ;
printf ("%d\n" , min ( del + x , tmp ) ) ;
}
}
return 0 ;
}C.快乐矩阵
把矩阵黑白间隔染色 \(:\)
你发现,每次一定是选择一个黑格子,一个白格子.
然后由于是矩阵,所以我们一定可以构造出一条从 \((1,1)\) 到 \((n,m)\) 的不重不漏的路径.
每次沿着这样的路径一路修改下去,每次操作把上一个格子清零,这样一定能推到最后.
到最后能置为全 \(0\) 的充要条件一定是黑格子之和等于白格子之和.
愉快 \(AC\) .
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 5e2 + 11 ;
int idx , res1 , res2 ;
int e[N][N] , n , m ;
bool stats[N] ;
signed main (int argc , char * argv[]) {
n = rint () ; m = rint () ;
rep ( i , 1 , n ) rep ( j , 1 , m ) e[i][j] = rint () ;
rep ( i , 1 , m ) stats[i] = stats[i-1] ^ 1 ;
rep ( i , 1 , n ) rep ( j , 1 , m ) {
if ( i & 1 ) {
if ( stats[j] ) res1 += e[i][j] ;
else res2 += e[i][j] ;
} else {
if ( stats[j] ) res2 += e[i][j] ;
else res1 += e[i][j] ;
}
}
puts ( res1 == res2 ? "Yes" : "No" ) ;
return 0 ;
}D.梦中的位运算
明白这样一个事实 \(:\)
\[x^2+y^2\le (x\&y)^2 + (x|y)^2\]
引理 \(:\)
\(1\)守恒定律 \(:\) 在该题目叙述的系统中,\(1\)既不会凭空产生也不会凭空消失,只会从一个元素转移到另一个元素,系统中 \(1\) 的代数和时时刻刻保持不变.(滑稽.jpg)
所以...你贪心地把所有 \(1\) 堆一起就好了...
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 1e5 + 100 ;
int n , v[N] , cnt[65] , g[65] , ans ;
vector < bool > tmp ;
inline void divide (int x) {
tmp.clear () ;
while ( x ) { tmp.pb ( x & 1ll ) ; x >>= 1ll ; }
// for (int k : tmp) printf ("%lld " , k ) ; puts ("") ;
for (int i = 0 ; i < tmp.size () ; ++ i)
if ( tmp[i] ) ++ cnt[i] ;
return ;
}
inline int quick (int a , int p) {
int res = 1ll ;
while ( p ) {
if ( p & 1ll ) res *= a ;
a *= a ; p >>= 1ll ;
}
return res ;
}
signed main (int argc , char * argv[]) {
n = rint () ; rep ( i , 1 , n ) v[i] = rint () ;
rep ( i , 0 , 62 ) g[i] = quick ( 2ll , i ) ;
rep ( i , 1 , n ) divide ( v[i] ) ;
// rep ( i , 0 , 4 ) printf ("%lldth : %lld\n" , i , cnt[i] ) ;
rep ( i , 1 , n ) {
int res = 0 ;
per ( j , 62 , 0 ) if ( cnt[j] ) -- cnt[j] , res += g[j] ;
v[i] = res ;
}
rep ( i , 1 , n ) ans += v[i] * v[i] ;
printf ("%lld\n" , ans ) ;
return 0 ;
}