A.
题意是n个人说出至少有x个人说谎,问合法撒谎的人数(不是唯一解)
暴力
#include<bits/stdc++.h>
#define ll long long
#define ls u<<1
#define rs u<<1|1
#define mm(x) memset(x,0,sizeof(x))
using namespace std;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
void YES(bool flag=true)
{
if(flag) puts("YES");
else puts("NO");
}
const int INF=998244353;
const int P=998244353;
const int N=1e6+5;
const int MX=1e6;
int fac[N];
int inv[N];
int ksm(int u,int v)
{
int res=1;
while(v)
{
if(v&1) res=(ll)res*u%P;
v>>=1; u=(ll)u*u%P;
}
return res;
}
int C(int n,int m)
{
if(m<0) return 0;
if(n<0) return 0;
return (ll)fac[n]*inv[m]%P*inv[n-m]%P;
}
void init_C()
{
fac[0]=1;
for(int i=1;i<=MX;++i) fac[i]=(ll)fac[i-1]*i%P;
inv[MX]=ksm(fac[MX],P-2);
for(int i=MX;i>=1;--i) inv[i-1]=(ll)inv[i]*i%P;
}
int T;
int n,m;
int a[N];
void solve(){
cin>>n;
bool f=false;
for(int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+1+n);
a[n+1]=n+1;
for(int i=0;i<=n;i++){
if(a[i]==a[i+1]) continue;
if(n-i>=a[i]&&n-i<a[i+1])
{
cout<<n-i<<"\n";
return ;
}
}
cout<<"-1\n";
}
int main()
{
cin>>T;
while(T--) solve();
return 0;
}
B.
题意:每个数mod x使得对称位置相同
a%x=b%x,根据同余定理
abs(a-b)是x的倍数
然后接下里求个共同最大的因子即可
#include<bits/stdc++.h>
#define ll long long
#define ls u<<1
#define rs u<<1|1
#define mm(x) memset(x,0,sizeof(x))
using namespace std;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
void YES(bool flag=true)
{
if(flag) puts("YES");
else puts("NO");
}
const int INF=998244353;
const int P=998244353;
const int N=1e6+5;
const int MX=1e6;
int fac[N];
int inv[N];
int ksm(int u,int v)
{
int res=1;
while(v)
{
if(v&1) res=(ll)res*u%P;
v>>=1; u=(ll)u*u%P;
}
return res;
}
int C(int n,int m)
{
if(m<0) return 0;
if(n<0) return 0;
return (ll)fac[n]*inv[m]%P*inv[n-m]%P;
}
void init_C()
{
fac[0]=1;
for(int i=1;i<=MX;++i) fac[i]=(ll)fac[i-1]*i%P;
inv[MX]=ksm(fac[MX],P-2);
for(int i=MX;i>=1;--i) inv[i-1]=(ll)inv[i]*i%P;
}
int T;
int n,m;
int ans;
int a[N];
void solve()
{
n=read(); ans=0;
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i)
{
int tmp=abs(a[i]-a[n+1-i]);
ans=__gcd(ans,tmp);
}
printf("%d\n",ans);
}
int main()
{
int T=read();
while(T--) solve();
return 0;
}
C.
题意:省略
手玩题
#include<bits/stdc++.h>
#define ll long long
#define ls u<<1
#define rs u<<1|1
#define mm(x) memset(x,0,sizeof(x))
using namespace std;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
void YES(bool flag=true)
{
if(flag) puts("YES");
else puts("NO");
}
const int INF=998244353;
const int P=998244353;
const int N=1e6+5;
const int MX=1e6;
int fac[N];
int inv[N];
int ksm(int u,int v)
{
int res=1;
while(v)
{
if(v&1) res=(ll)res*u%P;
v>>=1; u=(ll)u*u%P;
}
return res;
}
int C(int n,int m)
{
if(m<0) return 0;
if(n<0) return 0;
return (ll)fac[n]*inv[m]%P*inv[n-m]%P;
}
void init_C()
{
fac[0]=1;
for(int i=1;i<=MX;++i) fac[i]=(ll)fac[i-1]*i%P;
inv[MX]=ksm(fac[MX],P-2);
for(int i=MX;i>=1;--i) inv[i-1]=(ll)inv[i]*i%P;
}
int T;
int n,m;
int ans;
int a[N];
bool dfs(int n,int m)
{
if(n%m==0) return false;
return true;
}
void solve()
{
n=read(); m=read();
m=min(n,m);
//puts(dfs(n,m)? "YES":"NO");
//return ;
if(n==1)
{
puts("YES");
return ;
}
for(int i=2;i*i<=n;++i)
{
if(n%i==0)
{
if(i>m)
{
puts("YES");
return ;
}
if(i==m)
{
puts("NO");
return ;
}
int x=n/i;
int y=(n%i+(m-i)-1)/(m-i);
if(x>y)
{
puts("NO");
return ;
}
else
{
puts("YES");
return ;
}
break;
}
}
int i=n;
if(i>m)
{
puts("YES");
return ;
}
if(i==m)
{
puts("NO");
return ;
}
int x=n/i;
int y=(n%i+(m-i)-1)/(m-i);
if(x>y)
{
puts("NO");
return ;
}
else
{
puts("YES");
return ;
}
}
int main()
{
/*
int s=100;
for(int i=2;i<=100;++i)
{
cout<<"-------- "<<i<<endl;
for(int j=1;j<i;++j)
{
int x=s/j;
int y=(s%j+(i-j)-1)/(i-j);
if(x>y) cout<<j<<" ";
}
cout<<endl;
}
*/
int T=read();
while(T--) solve();
return 0;
}
D.
题意选个区间,然后答案就是这个区间的三个最大值之和减去区间长度+1
思路前后缀分解
枚举中间值
枚举左边最大值a[i]+i(i==l) 和右边最大值a[i]-i(i==r)
#include<bits/stdc++.h>
#define ll long long
#define ls u<<1
#define rs u<<1|1
#define mm(x) memset(x,0,sizeof(x))
using namespace std;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
void YES(bool flag=true)
{
if(flag) puts("YES");
else puts("NO");
}
const int INF=998244353;
const int P=998244353;
const int N=1e6+5;
const int MX=1e6;
int fac[N];
int inv[N];
int ksm(int u,int v)
{
int res=1;
while(v)
{
if(v&1) res=(ll)res*u%P;
v>>=1; u=(ll)u*u%P;
}
return res;
}
int C(int n,int m)
{
if(m<0) return 0;
if(n<0) return 0;
return (ll)fac[n]*inv[m]%P*inv[n-m]%P;
}
void init_C()
{
fac[0]=1;
for(int i=1;i<=MX;++i) fac[i]=(ll)fac[i-1]*i%P;
inv[MX]=ksm(fac[MX],P-2);
for(int i=MX;i>=1;--i) inv[i-1]=(ll)inv[i]*i%P;
}
int T;
int n,m;
int ans;
int a[N];
int l[N],r[N];
void solve()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
l[1]=a[1]+1;
for(int i=2;i<=n;i++){
l[i]=max(l[i-1],a[i]+i);
}
r[n]=a[n]-n;
for(int i=n-1;i>=1;i--){
r[i]=max(r[i+1],a[i]-i);
}
int mx=0;
for(int i=2;i<=n-1;i++){
mx=max(mx,a[i]+l[i-1]+r[i+1]);
//cout<<a[i]<<" "<<l[i-1]<<" "<<r[i+1]<<"\n";
}
cout<<mx<<"\n";
}
int main()
{
int T=read();
while(T--) solve();
return 0;
}
E.题意省略了
参考了A_G的bitset优化
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
using bs = bitset<N>;
int main () {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> m >> n;
vector<vector<int>> a(n, vector<int>(m+1));
for (int i = 0; i < n; i++) cin >> a[i][m];
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) cin >> a[i][j];
}
sort(a.begin(), a.end());
vector<bs> lower(n);
for (int i = 0; i < n; i++) lower[i].set();
vector<int> inds(n);
iota(inds.begin(), inds.end(), 0);
for (int i = 0; i < m; i++) {
sort(inds.begin(), inds.end(), [&] (int x, int y) {
return a[x][i] < a[y][i];
});
bs cur = 0;
int p = 0;
for (int j = 0; j < n; j++) {
while (a[inds[p]][i] < a[inds[j]][i]) cur.set(inds[p++], 1);
lower[inds[j]] &= cur;
}
}
vector<long long> dp(n);
for (int i = 0; i < n; i++) {
dp[i] = a[i][m];
for (int j = 0; j < i; j++) {
if (lower[i][j]) dp[i] = max(dp[i], dp[j]+a[i][m]);
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
}