A. Array Divisibility
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
inline ll read(){
ll x = 0 , f = 1 ;
char c = getchar() ;
while(c > '9' || c < '0'){
if(c == '-')
f = -1;
c = getchar() ;
}
while(c >= '0' && c <= '9'){
x = x * 10 + c - '0' ;
c = getchar() ;
}
return x * f ;
}
ll a[maxn] , t , n , m , k , l , r , cnt = 0 , b[maxn] ;
char s[maxn] , S[maxn] ;
void solve(){
n = read() ;
for(int i = 1 ; i <= n ; i ++){
cout << i << " " ;
}
cout << endl ;
}
int main(){
t = read() ;
while(t --){
solve() ;
}
return 0 ;
}
B. Corner Twist
题意：给你一个n*n矩阵，只包含1,2,3三个数字，可以选择一个一个矩形，将一个对角线同时加一，另一个对角线同时加2，将答案mod3，问能否将a数组变成b数组？
题解：直接枚举，添加数字，最后和b比较即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
inline ll read(){
ll x = 0 , f = 1 ;
char c = getchar() ;
while(c > '9' || c < '0'){
if(c == '-')
f = -1;
c = getchar() ;
}
while(c >= '0' && c <= '9'){
x = x * 10 + c - '0' ;
c = getchar() ;
}
return x * f ;
}
ll a[1000][1000] , t , n , m , b[1000][1000] ; ;
char s[maxn] , S[maxn] ;
void solve(){
n = read() ;
m = read() ;
for(int i = 1 ; i <= n ; i ++){
scanf("%s" , s + 1) ;
for(int j = 1 ; j <= m ; j ++){
a[i][j] = s[j] - '0' ;
}
}
for(int i = 1 ; i <= n ; i ++){
scanf("%s" , s + 1) ;
for(int j = 1 ; j <= m ; j ++){
b[i][j] = s[j] - '0' ;
}
}
for(int i = 1 ; i <= n - 1 ; i ++){
for(int j = 1 ; j <= m - 1 ; j ++){
if(a[i][j] != b[i][j]){
ll cnt = (b[i][j] + 3 - a[i][j]) % 3 ;
ll sum = 3 - cnt ;
a[i][j] += cnt ;
a[i][j] %= 3 ;
a[i + 1][j + 1] += cnt ;
a[i + 1][j +1] %= 3 ;
a[i][j + 1] += sum ;
a[i][j +1] %= 3 ;
a[i + 1][j] += sum ;
a[i + 1][j] %= 3 ;
}
}
}
bool f = 0 ;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= m ; j ++){
// cout << a[i][j] ;
if(a[i][j] != b[i][j]){
f = 1 ;
}
}
// cout << endl ;
}
if(f == 1){
cout << "NO\n" ;
return ;
}
cout << "YES\n" ;
}
int main(){
t = read() ;
while(t --){
solve() ;
}
return 0 ;
}
C. Have Your Cake and Eat It Too
题意：给你三个数组a,b,c，每个数组的和为tot，问能否找到三个[l,r]区间(a,b,c)，三个区间不相交，使得每个区间和都大于tot/3上取整。
题解：直接枚举abc三个顺序即可，一共有六种不同的组合，然后用二分来找到答案，记录即可。复杂度很低。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int maxn = 2e6 + 7 ;
inline ll read(){
ll x = 0 , f = 1 ;
char c = getchar() ;
while(c > '9' || c < '0'){
if(c == '-')
f = -1;
c = getchar() ;
}
while(c >= '0' && c <= '9'){
x = x * 10 + c - '0' ;
c = getchar() ;
}
return x * f ;
}
ll sa[maxn] , sb[maxn] , sc[maxn] ;
ll a[maxn] , t , n , m , k , l , r , b[maxn] , c[maxn] , d[maxn] , cnt = 6 ;
char s[maxn] , S[maxn] ;
void solve(){
n = read() ;
for(int i = 1 ; i <= n ; i ++){
a[i] = read() ;
}
for(int i = 1 ; i <= n ; i ++){
b[i] = read() ;
}
for(int i = 1 ; i <= n ; i ++){
c[i] = read() ;
}
for(int i = 1 ; i <= n ; i ++){
sa[i] = sa[i - 1] + a[i] ;
sb[i] = sb[i - 1] + b[i] ;
sc[i] = sc[i - 1] + c[i] ;
}
// cout << sa[n] << endl ;
ll K = (sa[n] + 3 - 1) / 3 ;
// cout << K<< endl ;
while(1){
ll rt = 1 ;
ll l = 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sa[mid] - sa[rt - 1] < K){
l = mid + 1 ;
}
else{
ans = mid ;
r = mid - 1 ;
}
}
// cout << ans << " " ;
d[1] = 1 ;
d[2] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
l = ans + 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sb[mid] - sb[rt - 1] < K){
l = mid + 1 ;
}
else{
r = mid - 1 ;
ans = mid ;
}
}
// cout << ans << endl ;
d[3] = rt ;
d[4] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
ll sum = 0 ;
sum += sc[n] - sc[rt - 1] ;
// cout << sum << endl ;
if(sum < K){
break ;
}
else{
d[5] = rt ;
d[6] = n ;
for(int i = 1 ; i <= cnt ; i ++){
cout << d[i] << " " ;
}
cout << endl ;
return ;
}
}
while(1){
ll rt = 1 ;
ll l = 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sa[mid] - sa[rt - 1] < K){
l = mid + 1 ;
}
else{
ans = mid ;
r = mid - 1 ;
}
}
d[1] = 1 ;
d[2] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
l = ans + 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sc[mid] - sc[rt - 1] < K){
l = mid + 1 ;
}
else{
r = mid - 1 ;
ans = mid ;
}
}
d[5] = rt ;
d[6] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
ll sum = 0 ;
sum += sb[n] - sb[rt - 1] ;
if(sum < K){
break ;
}
else{
d[3] = rt ;
d[4] = n ;
for(int i = 1 ; i <= cnt ; i ++){
cout << d[i] << " " ;
}
cout << endl ;
return ;
}
}
while(1){
ll rt = 1 ;
ll l = 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sb[mid] - sb[rt - 1] < K){
l = mid + 1 ;
}
else{
ans = mid ;
r = mid - 1 ;
}
}
d[3] = 1 ;
d[4] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
l = ans + 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sa[mid] - sa[rt - 1] < K){
l = mid + 1 ;
}
else{
r = mid - 1 ;
ans = mid ;
}
}
d[1] = rt ;
d[2] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
ll sum = 0 ;
sum += sc[n] - sc[rt - 1] ;
if(sum < K){
break ;
}
else{
d[5] = rt ;
d[6] = n ;
for(int i = 1 ; i <= cnt ; i ++){
cout << d[i] << " " ;
}
cout << endl ;
return ;
}
}
while(1){
ll rt = 1 ;
ll l = 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sb[mid] - sb[rt - 1] < K){
l = mid + 1 ;
}
else{
ans = mid ;
r = mid - 1 ;
}
}
d[3] = 1 ;
d[4] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
l = ans + 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sc[mid] - sc[rt - 1] < K){
l = mid + 1 ;
}
else{
r = mid - 1 ;
ans = mid ;
}
}
d[5] = rt ;
d[6] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
ll sum = 0 ;
sum += sa[n] - sa[rt - 1] ;
if(sum < K){
break ;
}
else{
d[1] = rt ;
d[2] = n ;
for(int i = 1 ; i <= cnt ; i ++){
cout << d[i] << " " ;
}
cout << endl ;
return ;
}
}
while(1){
ll rt = 1 ;
ll l = 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sc[mid] - sc[rt - 1] < K){
l = mid + 1 ;
}
else{
ans = mid ;
r = mid - 1 ;
}
}
d[5] = 1 ;
d[6] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
l = ans + 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sa[mid] - sa[rt - 1] < K){
l = mid + 1 ;
}
else{
r = mid - 1 ;
ans = mid ;
}
}
d[1] = rt ;
d[2] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
ll sum = 0 ;
sum += sb[n] - sb[rt - 1] ;
if(sum < K){
break ;
}
else{
d[3] = rt ;
d[4] = n ;
for(int i = 1 ; i <= cnt ; i ++){
cout << d[i] << " " ;
}
cout << endl ;
return ;
}
}
while(1){
ll rt = 1 ;
ll l = 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sc[mid] - sc[rt - 1] < K){
l = mid + 1 ;
}
else{
ans = mid ;
r = mid - 1 ;
}
}
d[5] = 1;
d[6] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
l = ans + 1 , r = n , ans = -1 ;
while(l <= r){
ll mid = (l + r) / 2 ;
if(sb[mid] - sb[rt - 1] < K){
l = mid + 1 ;
}
else{
r = mid - 1 ;
ans = mid ;
}
}
d[3] = rt ;
d[4] = ans ;
if(ans == -1){
break ;
}
rt = ans + 1 ;
ll sum = 0 ;
sum += sa[n] - sa[rt - 1] ;
if(sum < K){
break ;
}
else{
d[1] = rt ;
d[2] = n ;
for(int i = 1 ; i <= cnt ; i ++){
cout << d[i] << " " ;
}
cout << endl ;
return ;
}
}
cout << -1 << endl ;
}
int main(){
t = read() ;
while(t --){
solve() ;
}
return 0 ;
}
喜欢作者的记得点赞收藏加关注哦~
