1、1739B
0边界。当该点+-ai值都>=0则可出现多解 输出-1
#include <bits/stdc++.h>
#define endl '\n'
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
void s(){
int n;
cin >> n;
vector<int> d(n);
for(auto &i:d) {
cin >> i;
}
bool yes = 1;
vector<int> a(n);
a[0] = d[0];
for(int i = 1 ; i < n; i ++) {
a[i] = d[i] + a[i - 1];
if(a[i - 1] - d[i] >= 0 && d[i]) yes = 0;
}
if(yes) {
for(int i = 0 ; i < n ;i ++) cout << a[i] << " ";
cout << endl;
}else{
cout << -1 << endl;
}
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#endif
int t;
cin >> t;
for(;t;t--) s();
return 0;
}
2、1726B
太特判了。总结不好。
构造n个数，使得总和=m。并且这第i个数ai的pi定义为：所有比ai严格小的其他元素的共同异或，且要求pi=0（i=1---n）
1.n>m的不能构造，最低要求是n<=m
2.n偶数，m奇数的时候不能构造，因为成双对的时候好消，奇数值的存在导致前n-1个不好构造出现>0
3.n=1的时候就是m
4.m刚好整除n的时候，就是m/n
5如果n为奇数，那么前n-1个构造成1，最后一个补一个数使得和=m
6如果n为偶数，m为偶数，就每次都判断m-i能否整除n-i，如果不可以，那就输出1等着；如果可以，那就后面几个值都是(m-x)/(n-x) 这个x是当时成立的那个i
#include <bits/stdc++.h>
#define endl '\n'
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
//函数内初始化数组={}
/*
4
1 3
6 12
2 1
3 6
*/
void s(){
int n, m;
cin >> n >> m;
if(n > m) {
cout << "No\n";
return;
}
if(n % 2 == 0 && m & 1){
cout << "No\n";
return;
}
cout << "Yes\n";
if(n == 1) {
cout << m << endl;
return;
}
if(m % n == 0) {
// 刚好整除
for(int i = 1; i <= n; i ++){
cout << m / n << " ";
}cout << endl;
}else{ // 不能整除
if(n & 1){//强行构造偶数个1
{ // odd
for(int i = 1; i < n; i ++){
cout << 1 << " ";
}
cout << m - n + 1 << endl;
}
}else{
{ // even
for(int i = 1; i <= n; i ++){
if( (m - i) % 2 != 1 && (m - i) % (n - i) == 0){
cout << 1 << " ";
int out = (m - i) / (n - i);
i ++;
while(i <= n){
cout << out << " ";
i ++;
}cout << endl;
return;
}else{
cout << 1 << " ";
}
}
}
}
}
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t;
cin >>t;
for(;t;t--)s();
return 0;
}
3 、1708B
构造每个元素都是不同的gcd（i， ai）；
可以知道每个元素都是i的倍数。
那么怎么找落到L--R区间内的i的倍数呢？
别人的证明：if (L-i+1)/i * i <= R ,则就是该值，否则超出边界就是no；利用了向下取整的。
#include <bits/stdc++.h>
#define endl '\n'
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
void s(){
int n, l , r;
cin >> n >> l >> r;
bool yes = 1;
vector<int> ans(n + 1);
for(int j = 1; j <= n; j ++){
if((l + j - 1) / j * j <= r) {
ans[j] = (l + j - 1) / j * j;
}else {
yes = 0;
break;
}
}
if(yes){
cout << "YES\n";
for(int i = 1; i <= n; i ++) cout << ans[i] << " "; cout << endl;
}else{
cout << "NO\n";
}
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#endif
int t;
cin >> t;
for(;t;t--) s();
return 0;
}
