2021.11.25
CodeForces - 1471F 图论
// 每次先将染 1 的放进队列头部，染0的放尾
// 遍历染色即可
#include
#define ll long long
#define pii pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=3e5+7;
int T,n,m,u[qs],val[qs],cnt_1;
set st;
vector v[qs];
void bfs(int x){
deque q;
q.pb(x); u[x]=1,val[x]=1;
cnt_1++;
//
while(q.size()){
int t=q.front(); q.pop_front();
int flag=0;
for(int i=0;i
CodeForces - 1471D 数论，质因数分解
// 能放的一起的是 x*y 是平方数
// 把每一个数质因数分解，0喵过后合并
// 只有 0 1 s的区别
#include
#define ll long long
#define pii pair
#define fi first
#define se second
#define pb push_back
#define si size()
#define db double
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=1e6+7;
int pre[qs],u[qs],cnt=0,min_pre[qs];
void get_pre(){
for(int i=2;i=qs) break;
u[pre[j]*i]=1;
min_pre[pre[j]*i]=pre[j];
if(i%pre[j]==0) break;
}
}
}
int T,n,m,a[qs];
map< set ,int> mp;
map< set ,int>::iterator it;
int ans[3],cnt_1;
void solve(int x){
set st;
while(x>1){
int p=min_pre[x];
int ct=0;
while(x%p==0){
x/=p;
ct++;
}
if(ct&1) {
// cout<<"x="< st; st.insert(0);
ans[x]=1;
ans[x]=max(ans[x],mp[st]);
for(it=mp.begin();it!=mp.end();++it){
if(it->fi==st) continue;
if(it->fi!=st){
ans[x]=max(ans[x],it->se);
if((it->se)%2==0){
mp[st]+=it->se;
it->se=0;
}
}
}
}
int main(){
T=read();
get_pre();
while(T--){
n=read();
mp.clear();
cnt_1=0;
for(int i=1;i<=n;++i){
a[i]=read();
}
for(int i=1;i<=n;++i){
solve(a[i]);
}
// cout<<"**********\n";
//0
for(int i=0;i<2;++i) cal(i);
int q;
q=read();
while(q--){
ll x; x=read();
if(x>1) x=1;
cout<
[ E. AmShZ and G.O.A.T. ]( Problem - E - Codeforces (Unofficial mirror site, accelerated for Chinese users) ) 暴力+二分 思维
// 考虑3个数 a b c
// 要使这3个数是好的
// 满足 (a+b+c)/3>=b ==> c>=2*b-a
// 那枚举最小的那个数，二分找c，看序列最长长度
#include
#define ll long long
#define pii pair
#define fi first
#define se second
#define pb push_back
#define si size()
#define db double
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=1e6+7;
map mp;
map::iterator it;
int T,n,A[qs];
int main(){
T=read();
while(T--){
mp.clear();
n=read();
for(int i=1;i<=n;++i){
A[i]=read();
mp[A[i]]++;
}
int a,b,c,ans=0;
for(int i=1;i<=n;++i){
int len=0,id;
len+=mp[A[i]];
int flag=0;
a=A[i],b=a+1;
while(1){
if(!flag) c=a+1,flag=1;
else c=2*b-a;
//cout<<"c="<fi;
}
ans=max(ans,len);
}
cout<