「CF 1514A」Perfectly Imperfect Array
Link.
就看序列中是否存在不为平方数的元素即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
ll T,n,x;
bool check(ll x)
{
for(ll i=1;i*i<=x;++i) if(i*i==x) return true;
return false;
}
int main()
{
for(sf(T);T;--T)
{
sf(n);
bool fl=0;
for(int i=1;i<=n;++i)
{
sf(x);
if(!check(x)) fl=1;
}
if(fl) puts("YES");
else puts("NO");
}
return 0;
}「CF 1514B」AND 0, Sum Big
Link.
和最大的情况就是每个数都只有一个 $0$（二进制下），于是答案就是 $n^{k}$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
const int MOD=1e9+7;
int main()
{
int T,n,k;
for(sf(T);T;--T)
{
sf(n),sf(k);
ll ans=1;
for(int i=1;i<=k;++i) ans*=n,ans%=MOD;
pf(ans);
}
return 0;
}「CF 1514C」Product 1 Modulo N
Link.
把所有与 $n$ 互质的数拉出来，如果 product 不满足要求，就把最后一个剔除。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void sf(T &x){x=0;T f=0;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c^'0');if(f)x=-x;}
template<typename T>void pf(T x,char l='\n'){static T s[100],t;if(x<0)putchar('-'),x=-x;do s[++t]=x%10,x/=10;while(x);while(t)putchar(s[t--]^'0');putchar(l);}
int n;
ll op(ll x,ll y){return x*y%n;}
int main()
{
sf(n);
std::vector<ll> ans;
for(int i=1;i<=n;++i) if(__gcd(i,n)==1) ans.emplace_back(i);
if(accumulate(ans.begin(),ans.end(),1,op)!=1) ans.pop_back();
pf(ans.size());
for(int i:ans) pf(i,' ');
return 0;
}「CF 1514D」Cut and Stick
Link.
答案是 $\max\{1,2x-l\}$，$l$ 为区间长度，$x$ 为众数出现次数。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 5e5 + 5, MAXM = 720 + 5;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar( ) ( p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1 ++ )
template<typename _T>
void read( _T &x ){
x = 0; char c = getchar( ); _T f = 1;
while( c < '0' || c > '9' ){ if( c == '-' ) f = -1; c = getchar( ); }
while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar( ); }
x *= f;
}
template<typename _T>
void write( _T x ){
if( x < 0 ){ putchar( '-' ); x = -x; }
if( x > 9 ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
void swapp( _T &one, _T &another ){ int temp = one; one = another; another = temp; }
template<typename _T>
_T MIN( _T one, _T another ){ return one > another ? another : one; }
template<typename _T>
_T MAX( _T one, _T another ){ return one > another ? one : another; }
int N, M;
int cube, each, kase, isa[MAXN], cnt[MAXN], pos[MAXN], vis[MAXN], bel[MAXN];
int lps[MAXM], rps[MAXM], App[MAXM][MAXM];
vector<int> disc, fur[MAXN];
int getID( int x ){ return lower_bound( disc.begin( ), disc.end( ), x ) - disc.begin( ) + 1; }
void build( ){
memset( cnt, 0, sizeof( cnt ) );
for( int i = 1; i <= cube; ++ i ){
kase ++;
for( int j = i; j <= cube; ++ j ){
App[i][j] = App[i][j - 1];
for( int k = lps[j]; k <= rps[j]; ++ k ){
if( vis[isa[k]] != kase ) cnt[isa[k]] = 0;
cnt[isa[k]] ++; App[i][j] = MAX( App[i][j], cnt[isa[k]] );
vis[isa[k]] = kase;
}
}
}
memset( cnt, 0, sizeof( cnt ) );
}
int query( int opl, int opr ){
if( bel[opl] == bel[opr] ){
int res = 0; kase ++;
for( int i = opl; i <= opr; ++ i ){
if( vis[isa[i]] != kase ) cnt[isa[i]] = 0;
cnt[isa[i]] ++; res = MAX( res, cnt[isa[i]] );
vis[isa[i]] = kase;
}
return res;
}
int res = 0;
res = App[bel[opl] + 1][bel[opr] - 1];
for( int i = opl; i <= rps[bel[opl]]; ++ i ){
int lim = fur[isa[i]].size( ) - 1;
while( pos[i] + res <= lim && fur[isa[i]][pos[i] + res] <= opr ) res ++;
}
for( int i = lps[bel[opr]]; i <= opr; ++ i ){
while( pos[i] - res >= 0 && fur[isa[i]][pos[i] - res] >= opl ) res ++;
}
return res;
}
signed main( ){
read( N ); read( M ); each = 720; cube = ( N - 1 ) / each + 1;
for( int i = 1; i <= N; ++ i ){ read( isa[i] ); disc.push_back( isa[i] ); }
sort( disc.begin( ), disc.end( ) );
disc.erase( unique( disc.begin( ), disc.end( ) ), disc.end( ) );
for( int i = 1; i <= N; ++ i ){
isa[i] = getID( isa[i] );
fur[isa[i]].push_back( i );
pos[i] = fur[isa[i]].size( ) - 1;
}
for( int i = 1; i <= cube; ++ i ){
lps[i] = rps[i - 1] + 1; rps[i] = rps[i - 1] + each;
if( i == cube ) rps[i] = N;
for( int j = lps[i]; j <= rps[i]; ++ j ) bel[j] = i;
}
build( );
int opl, opr;
while( M -- > 0 ){
read( opl ); read( opr );
write( max( 1, 2 * query( opl, opr ) - ( opr - opl + 1 ) ) );
putchar( '\n' );
}
return 0;
}「CF 1514E」Baby Ehab's Hyper Apartment
Link.
// Oops, something went wrong.