A Era
题目
给一个长度为 (n) 的序列 (a_1,a_2,dots,a_n)，每次可以往序列中插入任意个整数，求最少插入多少个整数时 (forall i,a_ile i)。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool negt = false;
while(c < '0' || c > '9')
negt |= (c == '-') , c = getchar();
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return negt ? -re : re;
}
const int N = 110;
int n;
int a[N];
void solve() {
n = read();
for(int i = 1 ; i <= n ; i++)
a[i] = read();
int ans = 0;
for(int i = 1 ; i <= n ; i++)
ans = max(ans , a[i] - i);
cout << ans << endl;
}
int main() {
int T = read();
while(T--)solve();
}
B XOR Specia-LIS-t
题目
给定正整数序列(a_1,a_2,ldots ,a_n)将其划分为若干个连续子串,问是否存在一种方案,使得所有字串的最长上升子序列长度 的异或和为0.
思路
如果(n)是偶数,我们让一个数成为一个字串,异或和为0.
如果(n)是奇数,我们考虑找一个(i),使得(a_i>a_{i+1}),将(i)和(i+1)划分为一个字串,异或和也为0.
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool negt = false;
while(c < '0' || c > '9')
negt |= (c == '-') , c = getchar();
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return negt ? -re : re;
}
const int N = 1e5 + 10;
int n;
int a[N];
void solve() {
n = read();
for(int i = 1 ; i <= n ; i++)
a[i] = read();
bool flag = false;
for(int i = 2 ; i <= n ; i++)
if(a[i] <= a[i - 1]) {
flag = true;
break;
}
if(flag || (n & 1) == 0)
puts("YES");
else
puts("NO");
}
int main() {
int T = read();
while(T--)solve();
}
C Di-visible Confusion
题目
给一个长度为 (n) 的序列 (a_1,a_2,dots,a_n)，对于每个位置 (i)，如果 (a_i\%left(i+1 ight) ot=0)，就可以将 (a_i) 删掉。删掉之后，后面的数都会往前面移动一位。问能否将序列删成空。
思路
前面的删掉会影响后面,后面删掉不会影响前面.
对于一个(a_i),我们假设(a_1sim a_{i-1})都可以被删掉,我们考虑找一个位置(jin[1,i]),将(a_i)移动到(j)位置.如果存在一个(j),使得((j+1) mid a_i).就可以将(a_i)消掉.
换句话说,如果(1,2,3,ldots,j)都是(a_i)的约数,(a_i)就不能被消掉,即(operatorname{lcm}(2,3ldots,i+1)mid a_i)时,(a_i)不能被消掉,序列不能删空.
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool negt = false;
while(c < '0' || c > '9')
negt |= (c == '-') , c = getchar();
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return negt ? -re : re;
}
int gcd(int a , int b) {
return b == 0 ? a : gcd(b , a % b);
}
const int N = 1e5 + 10;
int n;
int a[N];
void solve() {
n = read();
for(int i = 1 ; i <= n ; i++)
a[i] = read();
int lcm = 1;
for(int i = 1 ; i <= n ; i++) {
lcm = lcm / gcd(lcm , i + 1) * (i + 1);
if(lcm > 1e9)break;
if(a[i] % lcm == 0) {
puts("NO");
return ;
}
}
puts("YES");
}
signed main() {
int T = read();
while(T--)solve();
}
D Moderate Modular Mode
题目
给定两个偶数(x,y).
求一个(nin[1,2 imes10^{18}])满足(n mod x=ymod n).
保证有解.
思路
先考虑简单的情况:
- (x=y),显然(n=x=y)是一个答案.
- (x > y),我们让(n>y),则有(ymod n=y),在让(nmod x=y)即可,(n=x+y)是一个答案.
- (x <y),我们还有(x,y)是偶数的条件没用上呢,然后我也不会了,传送门.
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool negt = false;
while(c < '0' || c > '9')
negt |= (c == '-') , c = getchar();
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return negt ? -re : re;
}
void solve() {
int x = read() , y = read();
if(x > y)cout << x + y << endl;
else if(x == y)cout << x << endl;
if(x < y)cout << y - y % x / 2 << endl;
}
signed main() {
int T = read();
while(T--)solve();
}