A
挺蠢的，无解条件为 \(n<k\) 或 \(x<k-1\)，即 \(\mathop{\mathrm{mex}}\not=k\)。先选 \(0\sim k-1\)，再选能选的最大值，当 \(x=k\)，选 \(x-1\)，否则选 \(x\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
void solve(){
int n,k,x;
read(n),read(k),read(x);
if(k-1>x||k>n){
puts("-1");
return;
}
int sum=(k-1)*k/2;
if(x==k){
sum+=(n-k)*(k-1);
}
else{
sum+=(n-k)*x;
}
write_endl(sum);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
B
分位讨论，如果一个或上一个 \(b_i\)，对于它二进制上的每一个 \(1\) 的位置有什么影响。若 \(n\) 为偶数，显然或上之后这一位一定为 \(0\)，否则一定为 \(1\)。
对于 \(n\) 为奇数时，所有数在或上一个 \(b_i\) 后异或和一定不会变小，对于 \(n\) 为偶数时，或上一个 \(b_i\) 后异或和一定不会变大，所以要么全或，要么全不或。直接计算两个极端的值，然后按 \(n\) 的奇偶性以不同的顺序输出两个数。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,m,a[N],b[N];
void solve(){
int xsum=0,osum=0;
read(n),read(m);
for(int i=1;i<=n;i++){
read(a[i]);
xsum^=a[i];
}
for(int j=1;j<=m;j++){
read(b[j]);
osum|=b[j];
}
if(n%2==1){
write_space(xsum);
int s=0;
for(int i=1;i<=n;i++){
s^=(a[i]|osum);
}
write_endl(s);
}
else{
int s=0;
for(int i=1;i<=n;i++){
s^=(a[i]|osum);
}
write_space(s);
write_endl(xsum);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
C
如果存在一个 \(j\) 满足 \(j\le i,a_j\ge a_i\)，\(a_i\) 答案的左侧和上方的界限要划到对应行和对应列，同理右侧和下方也一样。按权值从大到小找答案即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
vector<int>sum[N];
int n,a[N],k,ans[N];
void solve(){
read(n),read(k);
for(int i=1;i<=k;i++){
sum[i].clear();
}
for(int i=1;i<=n;i++){
read(a[i]);
sum[a[i]].pb(i);
}
int mn=n+1,mx=0;
for(int i=k;i>=1;i--){
if(sum[i].size()==0){
ans[i]=0;
continue;
}
mn=min(mn,sum[i].front());
mx=max(mx,sum[i].back());
ans[i]=(mx-mn+1)*2;
}
for(int i=1;i<=k;i++){
write_space(ans[i]);
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
D
因为要字典序最大，我们最基本要让 \(1\) 的值最大，找到代价最小的位置，如果有多个代价最小的位置，选最后一个位置，令该位置为 \(p\)，这样可以使得答案其它位置的答案也更大。如果此时还有多余的代价，因为 \(p\) 以前的位置都已经尽量大了，所以我们只能考虑将一些 \(p\) 处的贡献往后移动到代价更大的位置产生贡献，将所有的代价减去 \(p\) 后，能够发现这还是上述操作，重复进行操作直到 \(p=n\) 为止。看得出来，这个操作序列 \(p\) 的代价的序列就是原序列的单调栈中的权值，维护一个单调上升的单调栈就行。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,c[N],k,cnt[N],stk[N],top;
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(c[i]);
cnt[i]=0;
}
read(k);
top=0;
for(int i=1;i<=n;i++){
while(top&&c[stk[top]]>=c[i]){
top--;
}
stk[++top]=i;
}
cnt[0]=inf;
for(int i=1;i<=top;i++){
cnt[stk[i]]=min(cnt[stk[i-1]],k/(c[stk[i]]-c[stk[i-1]]));
cnt[stk[i-1]]-=cnt[stk[i]];
k-=cnt[stk[i]]*(c[stk[i]]-c[stk[i-1]]);
}
for(int i=n-1;i;i--){
cnt[i]+=cnt[i+1];
}
for(int i=1;i<=n;i++){
write_space(cnt[i]);
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
E
令 \(f_{i,j}\) 表示前 \(i\) 个位置中能得否划分处若干个区间使得 \(\mathop{\mathrm{mex}}\) 异或得到 \(j\)。
可以用 \(O(n^2)\) 的复杂度处理出区间 \([i,j]\) 的 \(\mathop{\mathrm{mex}}\)。为了保证复杂度，需要去重，只存下 \(\mathop{\mathrm{mex}}_{[i,j]}/not=\mathop{\mathrm{mex}}_{[i,j-1]}\) 且 \(\mathop{\mathrm{mex}}_{[i,j]}/not=\mathop{\mathrm{mex}}_{[i+1,j]}\) 的 \(\mathop{\mathrm{mex}}\)。这样的 \(\mathop{\mathrm{mex}}_{[i,j]}\) 的数量是 \(O(n)\) 级别的。\(j\) 的可以转移来的位置只有存下来的 \(\mathop{\mathrm{mex}}_{[i,j]}\) 所对应的 \(i-1\)。复杂度就变成了 \(O(nV)\) 级别了。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e3+10,M=8192+10;
int n,a[N],mex[N][N],cnt[M];
bool f[N][M];
vector<pii>num[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
int mx=*max_element(a+1,a+n+1);
for(int i=0;;i++){
if((1<<i)>mx+1){
mx=(1<<i)-1;
break;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=mx;j++){
cnt[j]=0;
}
int pos=0;
for(int j=i;j<=n;j++){
cnt[a[j]]++;
while(cnt[pos]){
pos++;
}
mex[i][j]=pos;
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(mex[i][j]!=mex[i][j-1]&&mex[i][j]!=mex[i+1][j]){
num[j].pb(mp(i,mex[i][j]));
}
}
}
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=mx;j++){
f[i][j]=f[i-1][j];
if(f[i-1][j]){
continue;
}
for(auto x:num[i]){
int pre=x.first,nxt=x.second;
f[i][j]|=f[pre-1][j^nxt];
}
}
}
for(int i=mx;i>=0;i--){
if(f[n][i]){
write_endl(i);
break;
}
}
for(int i=0;i<=mx;i++){
cnt[i]=0;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=mx;j++){
f[i][j]=0;
}
for(int j=0;j<=n;j++){
mex[i][j]=0;
}
num[i].clear();
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
F
考虑将 \(1\sim n\) 全部化为 \(k\) 进制，将其放到trie上，可以发现两种数列b分别为bfs序和dfs序得到的数列，答案要找的数就是bfs序减dfs序结果为 \(0\) 的点。考虑将trie拆成若干行，对于每行计算答案，可以二分找到贡献答案的范围。总复杂度 \(O(t\log n^3)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int __int128
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
int n,k,tot,L[100],R[100],ans;
void init(){
ans=0,tot=0;
for(int l=1,r;l<=n;l=r+1){
r=min(l*k-1,n);
L[++tot]=l,R[tot]=r;
}
}
int get(int x,int cur){
int ans=-x+1,mul=1;
for(int i=cur-1;i;i--){
mul=mul*k;
ans+=x/mul-L[i]+1;
}
mul=1;
for(int i=cur;i<=tot;i++){
ans+=min(x*mul-1,n)-L[i]+1;
mul*=k;
}
return ans;
}
void solve(){
read(n),read(k);
if(n<k){
write_endl(n);
return;
}
init();
for(int i=1;i<=tot;i++){
int ansl=R[i]+1,ansr=R[i]+1;
int l=L[i],r=R[i];
while(l<=r){
int mid=(l+r)>>1;
if(get(mid,i)>=0){
ansl=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
l=L[i],r=R[i];
while(l<=r){
int mid=(l+r)>>1;
if(get(mid,i)>0){
ansr=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
ans+=ansr-ansl;
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}