A.Strange Birthday Party
给定m个物品和价值，保证非递减，每个物品只能被选择一次，有n个人，每个人有一个k，代表他只能选择编号小于等于k的物品，或者直接花费\(c_k\)，求最少总花费。
考虑贪心，让k最大的人选择最前面的物品，这样无法选择物品的人都是k较小的，这样其选择花费\(c_k\)也比较优。
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=3e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int k[N],c[N];
int vis[N];
void work()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&k[i]);
}
for(int i=1;i<=m;i++){
scanf("%d",&c[i]);
vis[i]=0;
}
sort(k+1,k+n+1);
int now=1;
ll ans=0;
for(int i=n;i>=1;i--){
while(now<=m&&vis[now]){
now++;
}
if(now==m+1){
ans+=c[k[i]];
}else{
if(now<=k[i]){
ans+=c[now];
vis[now]=1;
}else{
ans+=c[k[i]];
}
}
}
printf("%lld\n",ans);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
B.Strange Definition
定义相邻为\(lcm(a_i,a_j)/gcd(a_i,a_j)\)为完全平方数（包括自己），在每一秒，每个数会变成与其相邻数的乘积，记\(d_i\)为与第i个数相邻的数的数量，每次询问第x秒\(max(d_{\sum_{i=1}^n d_i})\)
可以发现，对于一些相邻的数，如果有偶数个，那么过去一秒后其会变成完全平方数，使得所有完全平方数都相邻，如果有奇数个，获得的乘积中奇数个的质因数还是那几个，还是只有这些数相邻。所以只需要区分0秒和其他时间。如何快速求某个数相邻的数量，考虑每个数中偶数个的质因数都无用，只考虑保留奇数个的质因子，且只保留一个，那么相邻的数都会变成相同的数，用一个数组记录即可。0秒时即为这个数组中的最大值，1秒时要记录所有偶数个相邻数的和（注意1也是完全平方数，奇数时也加入），与奇数个相邻数求最大值即可。
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int prime[N];
int pri[N];
int tot=0;
int a[N];
int vis[N];
void pre(int n)
{
tot=0;
prime[1]=1;
for(int i=2;i<=n;i++){
if(!prime[i]){
pri[++tot]=i;
}
for(int j=1;j<=tot&&i*pri[j]<=n;j++){
prime[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
void work()
{
int n;
scanf("%d",&n);
int sum=0;
int ans=0;
int ans2=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
int x=a[i];
int tmp=1;
for(int j=1;j<=tot&&1ll*j*j<=x;j++){
if(x%pri[j]==0){
int cnt=0;
while(x%pri[j]==0){
x/=pri[j];
cnt^=1;
}
if(cnt==1){
tmp*=pri[j];
}
}
}
if(x!=1){
tmp*=x;
}
//printf("%lld\n",tmp);
vis[tmp]++;
ans=max(ans,vis[tmp]);
ans2=max(ans,vis[tmp]);
if(vis[tmp]%2==0){
sum+=vis[tmp];
}else{
sum-=vis[tmp]-1;
}
}
if(vis[1]%2==1){
sum+=vis[1];
}
ans2=max(ans2,sum);
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
ll x;
scanf("%lld",&x);
if(x==0){
printf("%d\n",ans);
}else{
printf("%d\n",ans2);
}
}
for(int i=1;i<=n;i++){
//scanf("%d",&a[i]);
int x=a[i];
int tmp=1;
for(int j=1;j<=tot&&1ll*j*j<=x;j++){
if(x%pri[j]==0){
int cnt=0;
while(x%pri[j]==0){
x/=pri[j];
cnt^=1;
}
if(cnt==1){
tmp*=pri[j];
}
}
}
if(x!=1){
tmp*=x;
}
//printf("%lld\n",tmp);
vis[tmp]--;
}
}
int main()
{
pre(1e6);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
C.Strange Shuffle
给定一个序列，初始都为k，每次询问后，每个数会向其前一个给x/2向下取整，向后一个给x/2向上取整，其中有一个特殊的位置p，其只会将所有的x丢给后一个数，现在可以询问1000次，每次可以询问某一个位置的值，要求找到这个p位置。
首先可以稍微模拟一下，发现p的两端受其影响的数的数量是操作数，其左边都是小于他的，其右边都是大于他的。那么只要找到一个与k不相等的位置，然后就可以得到p的区间然后二分查找即可。那么现在问题就是如果在一定次数内找到与k不相等的数。考虑每次询问后，所受到的区间影响序列为[3,5,7,9,11,……]，然后为了不重复访问某些位置，将这些长度不相交地放到序列中，这样实测只需要300多次可以将序列访问完，如果找的所有点都是k，那么再按当前放入的最长长度继续查询，只需要200不到次。如果还是没有查到，那么只会有我们当前点是p或者p的对面，当n为偶数时，无论多少次，p的对面是k。那么考虑当前点的左边是否小于k，然后就可以判断当前点是p还是p的对面。
oh，我是菜鸡，前面瞎跑，将长度扩大到一定后，跑后面那个就可以了，类似于根号做法。
emmmm，好像直接rand找也可以（555555555）。
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int n,k;
int qy(int x)
{
printf("? %d\n",x);
fflush(stdout);
int y;
scanf("%d",&y);
return y;
}
void find(int x,int y)
{
int l=x,r=y;
while(l<=r){
int m=(l+r)>>1;
int cnt=qy((m+10*n-1)%n+1);
if(cnt<k){
l=m+1;
}else if(cnt>k){
r=m-1;
}else{
printf("! %d\n",(m+10*n-1)%n+1);
return;
}
}
}
void work()
{
scanf("%d%d",&n,&k);
qy(1);
int cnt=2;
for(int i=1;i<=n;i+=cnt){
int now=qy(i);
if(now<k){
find(i,i+(cnt)/2);return;
}else if(now>k){
find(i-(cnt)/2,i);return;
}
cnt+=2;
}
int ans=2;
int cnt1=cnt;
for(int i=2;i<=n;i+=cnt1){
int now=qy(i);
if(now<k){
find(i,i+(cnt)/2);return;
}else if(now>k){
find(i-(cnt)/2,i);return;
}
cnt+=2;
cnt=min(cnt,n+1);
}
if(qy(ans-1)<=k&&qy(ans-1)<=k){
printf("! %d\n",ans);
}else{
ans=(ans+n/2-1)%n+1;
printf("! %d\n",ans);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
D.Strange Housing
给定一张图，要在图中选定一些点，若一条边的两端都没有被选到，这条边会被删掉，要求最后不存在一条边两端都被选到，并且所有点互通。
一开始想到了一般图最大独立集，然后发现并没有要求数量，所以直接dfs染色即可，需要判断一下图是否连通。（为什么这么简单的题会出在div1D，最后十分钟写还少了清空）
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=3e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<int>v[N];
int vis[N];
int fa[N];
int ans[N];
int find(int x)
{
if(fa[x]!=x)return fa[x]=find(fa[x]);
return x;
}
void uni(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y){
fa[x]=y;
}
}
void dfs(int x)
{
vis[x]=1;
bool f=1;
for(auto y:v[x]){
if(ans[y]){
f=0;break;
}
}
if(f){
ans[x]=1;
}
for(auto y:v[x]){
if(!vis[y]){
dfs(y);
}
}
}
void work()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
v[i].clear();
vis[i]=0;
fa[i]=i;
ans[i]=0;
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
uni(x,y);
}
for(int i=2;i<=n;i++){
if(find(i)!=find(i-1)){
printf("NO\n");return;
}
}
dfs(1);
int sum=0;
for(int i=1;i<=n;i++){
if(ans[i])sum++;
}
printf("YES\n");
printf("%d\n",sum);
for(int i=1;i<=n;i++){
if(ans[i]){
printf("%d ",i);
}
}
printf("\n");
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}