24.9.29

星期一：

补 cf round974 div3 H cf传送门

题意：给一数组，q次询问，每次询问l-r区间内是否每个数字都出现偶数次

终于找到了梦中的随机数函数，这随机数真是非常顶级口牙

思路：众所周知异或前缀和可以除掉出现偶数次的数字，但直接异或前缀和很容易出错，比如1 2 3，我们给每个ai赋一个随机数，这样就会大大减少出错的概率

代码如下：

mt19937_64 rnd(time(0));const int N=2.2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll a[N];
void solve(){int q; cin >> n >> q;map<int,ll>mp;for(int i=1;i<=n;i++){cin >> a[i];if(!mp.count(a[i])) mp[a[i]]=rnd();a[i]=mp[a[i]];a[i]^=a[i-1];}while(q--){int l,r; cin >> l >> r;if(a[r]^a[l-1]) cout << "NO\n";else cout << "YES\n";}
}

既然找到了梦中情数，那就不得不来试试之前那道状压，看能不能用随机数加逆康托冲过去

上链接 cf传送门

很典的状压dp，上周就想用随机+逆康托看能不能冲过去，可惜受限于初始rand()函数太拉跨

今时不同往日，有了无敌的 mt19937_64 rnd(time(0))，看我一举冲破敌人的数据

调了两次cnt，由于逆康托费拉不堪的n^2复杂度，跑2e6与1e6次会T，不过1e5足矣

代码如下：

mt19937_64 rnd(time(0));const int N=2.2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;ll rng(ll l,ll r){return rnd()%(r-l+1)+l;
}
ll fac[N];
vector<int> rev_kt(ull k,int len){             //编号和排列长度vector<int>ans;k--;vector<int>ve;for(int i=1;i<=len;i++) ve.push_back(i);for(int i=1;i<=len;i++){int t=k/fac[len-i];ans.push_back(ve[t]);ve.erase(ve.begin()+t);k%=fac[len-i];}return ans;
}
void solve(){fac[0]=1;for(int i=1;i<=13;i++) fac[i]=fac[i-1]*i;int w; cin >> n >> w;map<int,int>mp;for(int i=1;i<=n;i++){int len; cin >> len;mp[len]++;}vector<int>ve; ve.push_back(0);for(auto [x,y]:mp) ve.push_back(y);int sz=mp.size();set<ll>st;int cnt=1e5,ans=13;while(cnt--){ll idx=rng(1,fac[sz]);if(st.find(idx)!=st.end()) continue;st.insert(idx);auto p=rev_kt(idx,sz);int day=1,lef=w;for(int i:p){if(ve[i]>lef) lef=w-ve[i],day++;else lef-=ve[i];if(day>=ans) break;}ans=min(day,ans);if((ll)st.size()==fac[sz]) break;}cout << ans;
}

逆康托。。感觉不如shuffle()函数，比逆康托快了200ms

代码如下：

mt19937_64 rnd(time(0));const int N=2.2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;void solve(){int w; cin >> n >> w;map<int,int>mp;for(int i=1;i<=n;i++){int len; cin >> len;mp[len]++;}vector<int>ve; ve.push_back(0);for(auto [x,y]:mp) ve.push_back(y);int sz=mp.size();vector<int>p;for(int i=1;i<=sz;i++) p.push_back(i);int cnt=1e5,ans=13;while(cnt--){shuffle(p.begin(),p.end(),rnd);int day=1,lef=w;for(int i:p){if(ve[i]>lef) lef=w-ve[i],day++;else lef-=ve[i];if(day>=ans) break;}ans=min(day,ans);}cout << ans;
}

不过24百度之星决赛的状压无法用随机数冲过去，21！太大，ac概率跟买彩票差不多

学而时习之，不亦乐乎，重做道经典主席树牛客传送门

思路：之前的文章已有：csdn传送门，此处不再赘述

代码方面看了下和上次的差别不大，除了fnd_sum写的更精简了些

不过太久没写主席树，这次写了个幽默的pushup()，还有ed给取成max了

代码如下：

const int N=6e5+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
int a[N];
const int MAXN=6e5+10;
struct seg_Tree{
#define lc(p) t[p].ch[0]
#define rc(p) t[p].ch[1]struct nod{int ch[2];int sum,ed;}t[N*22];int tot,root[N];void insert(int x,int &y,int l,int r,int qv,int i){y=++tot; t[y]=t[x]; t[y].sum++;if(l==r){t[y].ed=i;return ;}int mid=l+r>>1;if(qv<=mid) insert(lc(x),lc(y),l,mid,qv,i);if(qv>mid) insert(rc(x),rc(y),mid+1,r,qv,i);t[y].ed=min(t[lc(y)].ed,t[rc(y)].ed);}int fnd_mex(int y,int l,int r,int ql){if(l==r) return l;int mid=l+r>>1;if(t[lc(y)].ed<ql) return fnd_mex(lc(y),l,mid,ql);else return fnd_mex(rc(y),mid+1,r,ql);}int fnd_sum(int x,int y,int l,int r,int qv){if(r<=qv) return t[y].sum-t[x].sum;int mid=l+r>>1;int res=0;res+=fnd_sum(lc(x),lc(y),l,mid,qv);if(qv>mid) res+=fnd_sum(rc(x),rc(y),mid+1,r,qv);return res;}
}tr;
void solve(){cin >> n;map<int,int>to;int cnt=0;for(int i=1;i<=n;i++){cin >> a[i];to[a[i]]=1;to[a[i]+1]=1;}for(auto &[x,y]:to) y=++cnt;for(int i=1;i<=n;i++) tr.insert(tr.root[i-1],tr.root[i],1,MAXN,to[a[i]],i);int q; cin >> q;while(q--){int l,r; cin >> l >> r;int mex=tr.fnd_mex(tr.root[r],1,MAXN,l);int sum=tr.fnd_sum(tr.root[l-1],tr.root[r],1,MAXN,mex);cout << r-l+1-sum << "\n";}
}

补 cf round 973 div2 D cf传送门

曾作为牛客多校的签到题出现过，不过那题数据范围100以内

思路：易想到只要存在 ai > ai+1，就操作，最后是个单调不减，不过数据范围不允许暴力抹平，可以二分出最大的最小值和最小的最大值，来取得最小极差

代码如下：

const int N=3e5+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll a[N];
bool check1(ll x){ll sum=0;for(int i=1;i<=n;i++){if(a[i]>x) sum+=a[i]-x;else if(sum<x-a[i]) return 0;else sum-=x-a[i];}return 1;
}
bool check2(ll x){ll sum=0;for(int i=1;i<=n;i++){if(a[i]>x) sum+=a[i]-x;else sum-=x-a[i],sum=max(0ll,sum);}return sum==0;
}
void solve(){cin >> n;ll mi=1e18,ma=0;for(int i=1;i<=n;i++){cin >> a[i];mi=min(a[i],mi);ma=max(a[i],ma);}ll ans1=0,ans2=0;ll l=mi,r=ma;while(l<=r){ll mid=l+r>>1;if(check1(mid)) ans1=mid,l=mid+1;else r=mid-1;}l=mi,r=ma;while(l<=r){ll mid=l+r>>1;if(check2(mid)) ans2=mid,r=mid-1;else l=mid+1;}cout << ans2-ans1 << "\n";
}

星期二：

cf edu round134 div2 D 位运算贪心 cf传送门

思路：易想到从高位向低位贪心，ans怎样能在这位上为1呢，需要a中此位为0的数与b中此位为1的数能一一对应，即数量相等，反过来也是一样，若ans此位为1，接下来需要把a和b按此位01对应分为两组，以后每一低位需在每个小组内递推找对应。思路上不难，但代码如何实现是个问题

这里用到了神奇的sort，首先将a从小到大排，将b从大到小排，为什么这么做呢，将每个数看作二进制，排序时一定先按优先级最高的第一位来排，也就是如果a中最高位的0/1数量刚好能和b中最高位的1/0数量对应，那么一定存在 idx，使得任意i<=idx，ai此位为0，bi此位为1，任意i>=idx，ai此位为1，bi此位为0。

利用这点，我们就无形中做到了分组，如果ans此位不能为1，就将a，b所有数此位全设为0或1，重新排序，避免以后低位时受到这一位对排序的影响，如果能为1，就保留原来情况

代码如下：

const int N=2e5+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
int a[N],b[N];
void solve(){cin >> n;for(int i=1;i<=n;i++) cin >> a[i];for(int i=1;i<=n;i++) cin >> b[i];sort(a+1,a+n+1);sort(b+1,b+n+1,greater<>());int ans=0;for(int i=30;~i;i--){bool if1=1;for(int j=1;j<=n;j++) if((a[j]&1<<i)==(b[j]&1<<i)){if1=0; break;}if(if1) ans|=1<<i;else{for(int j=1;j<=n;j++) a[j]|=1<<i,b[j]|=1<<i;sort(a+1,a+n+1);sort(b+1,b+n+1,greater<>());}}cout << ans << "\n";
}

星期三：

补 23 CCPC秦皇岛 F cf传送门

首先注意读题，ai属于正整数集合，也就是说不能把ai改成0

思路：这题有一个大胆的前置结论，对于奇偶性相同的x，y，存在无穷个z使得x+z与y+z为质数

也就是说，若 ai-1与ai+1奇偶性相同，修改ai一定能满足ai+ai-1与ai+ai+1都为质数。实际上这题和石碑文很像，都是先定义状态，然后大力分类讨论来转移

题解定了4个状态，我自己定了7个

1-改为1，2-改为2，3-改为任意奇数，4-改为任意偶数，5-不变，6-改为质数-1，7-改为质数-2

注意分类讨论需要比较细

代码如下：

const int N=2e6+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
int dp[N][8];
int p[N],idx;
bool vi[N];
void getp(int x){for(int i=2;i<=x;i++){if(!vi[i]) p[++idx]=i;for(int j=1;1ll*i*p[j]<=x;j++){vi[i*p[j]]=1;if(i%p[j]==0) break;}}
}
void solve(){getp(2e5+10);cin >> n;int lst=0;cin >> lst;memset(dp,0x3f,sizeof dp);dp[1][1]=(lst!=1);dp[1][2]=(lst!=2);dp[1][3]=dp[1][4]=1;dp[1][5]=0;dp[1][6]=vi[lst+1];dp[1][7]=vi[lst+2];for(int i=2;i<=n;i++){int a; cin >> a;dp[i][1]=min({dp[i-1][1],dp[i-1][2],dp[i-1][4],dp[i-1][6]})+(a!=1);dp[i][2]=min({dp[i-1][1],dp[i-1][3],dp[i-1][7]})+(a!=2);if(lst&1) dp[i][3]=dp[i-1][4]+1,dp[i][4]=min(dp[i-1][3],dp[i-1][5])+1;else dp[i][3]=min(dp[i-1][4],dp[i-1][5])+1,dp[i][4]=dp[i-1][3]+1;dp[i][3]=min(dp[i-1][2]+1,dp[i][3]);dp[i][4]=min(dp[i-1][1]+1,dp[i][4]);if(a==1) dp[i][5]=min({dp[i-1][1],dp[i-1][2],dp[i-1][4],dp[i-1][6]});else if(a==2) dp[i][5]=min({dp[i-1][1],dp[i-1][3],dp[i-1][7]});else{if(a&1) dp[i][5]=dp[i-1][4];else dp[i][5]=dp[i-1][3];}if(!vi[lst+a]) dp[i][5]=min(dp[i-1][5],dp[i][5]);if(!vi[a+1]) dp[i][5]=min(dp[i-1][1],dp[i][5]),dp[i][6]=dp[i][5];if(!vi[a+2]) dp[i][5]=min(dp[i-1][2],dp[i][5]),dp[i][7]=dp[i][5];dp[i][6]=min(dp[i-1][1]+(vi[a+1]),dp[i][6]);dp[i][7]=min(dp[i-1][2]+(vi[a+2]),dp[i][7]);lst=a;}cout << *min_element(dp[n]+1,dp[n]+8) << "\n";
//	for(int j=1;j<8;j++) cout << j << " \n"[j==7];
//	cout << "\n";
//	for(int i=1;i<=n;i++)
//		for(int j=1;j<8;j++) cout << dp[i][j] << " \n"[j==7];
}

补 24 ICPC武汉邀请赛 F 难得交互 cf传送门

思路:二分答案，如何check是个问题，从左下角开始走，若当前元素<=mid，则同列以上所有数都<=mid，sum加上行数，往右走，若当前元素>mid，则往上走，步数最多 2*n，再加个log1e6，询问在4e4之内

代码如下:

const int N=2e6+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll ask(int x,int y,ll mid){cout << "? " << x << " " << y << " " << mid << endl;bool ifx=0; cin >> ifx;return ifx;
}
void solve(){ll k; cin >> n >> k;k=n*n-k+1;ll l=1,r=n*n,ans=0;while(l<=r){ll mid=l+r>>1;int px=n,py=1,sum=0;while(px && py<=n){if(ask(px,py,mid)) sum+=px,py++;else px--;}if(sum>=k) ans=mid,r=mid-1;else l=mid+1;}cout << "! " << ans;
}

贴道 B cf传送门

平心而论并不算难的贪心题，但赛时这题花了3h

思路：从高位到低位放，放这位的前提是低位放满都不够，放的话尽量这位多放点

代码如下：

void solve(){cin >> n;ll sum=0;for(int i=1;i<=n;i++){int a; cin >> a;sum+=a;}ll ans=0;for(int i=31;~i;i--){ll one=1ll<<i;if(one>sum) continue;ll ma=((1ll<<i)-1)*n;if(ma<sum){ans|=1<<i;sum-=min(n,sum/one)*one;}}cout << ans;
}

星期四：

补24 ICPC武汉邀请赛 M cf传送门

思路：注意到合并操作必定是一奇一偶合成一个奇数，所以偶数是用一个少一个，可以把偶数从大到小来考虑，例如 num是一偶数，应优先看有无 num+1或能否合成，若无，再检查 num-1

如何判断能否得到数 num+1呢，已知num+1可确定由num0和num1合成，若无num0，那么肯定无法合成，若还有num0，再判断能否得到num1。相信聪明的你已经发现了，判断可用递推递归实现

记录数的数量用map，注意带着map跑dfs时别 RE了

代码如下：

ll n;
map<ll,int>mp;
bool dfs(ll num){ll num0=num/2,num1=num/2;if(num0&1) num0++;else num1++;              //找出由哪俩数合成if(mp[num0]<=0) return 0; //先看最重要偶数mp[num0]--;               //若有,先给扣掉,以免影响递推的dfs判断if(mp[num1]>0 || dfs(num1)){mp[num1]--,mp[num]++;n--;return 1;}else{mp[num0]++;       //无法合成,记得给num0还回来return 0;}
}
void solve(){cin >> n;vector<ll>ve;for(int i=1;i<=n;i++){ll a; cin >> a;mp[a]++;if(!(a&1)) ve.push_back(a);}sort(ve.begin(),ve.end(),greater<>());for(ll num:ve) if(mp[num]>0){mp[num]--;if(mp[num+1]>0 || dfs(num+1)) mp[num+1]--,mp[num*2+1]++,n--;else if(mp[num-1]>0 || dfs(num-1)) mp[num-1]--,mp[num*2-1]++,n--;else mp[num]++;}cout << n << "\n";for(auto [x,y]:mp) for(int i=1;i<=y;i++) cout << x << " ";
}

星期五：

补 D cf传送门

注意题目有说明，异或只是输出答案的方式，与解法无关

思路：g【i】【j】表示从 i开始走 j步不折返的最大价值，f【i】【j】表示折返一次

先处理出 g的值，将 f的左右折返分开看，f【i】【j】若向左折返一步，则等于g【i-1】【j-1】，折返两步等于g【i-2】【j-2】，以此类推，若向右折返一步等于g【i+1】【j-1】，两步为g【i+2】【j-2】，以此类推

到这即可使用n^2枚举 i，j，同时g【i】【j】一直向上个状态取最大值，即可处理出f

注释语句也可处理出 f

代码如下：

ll n;
ll a[5050];
ll f[5050][5050*2],g[5050][5050*2];
void solve(){cin >> n;for(int i=1;i<=n;i++){cin >> a[i];a[i]+=a[i-1];}for(int i=1;i<=n;i++){for(int j=1;j<=2*n;j++){int l=max(i-j,1),r=min(1ll*i+j,n);g[i][j]=max(a[i]-a[l-1],a[r]-a[i-1]);}}for(int i=1;i<=n;i++){for(int j=1;j<=2*n;j++){g[i][j]=max(g[i-1][j-1],g[i][j]);f[i][j]=g[i][j];
//			f[i][j]=max(f[i-1][j-1],g[i][j]);}}for(int i=n;i;i--){for(int j=1;j<=2*n;j++){g[i][j]=max(g[i+1][j-1],g[i][j]);f[i][j]=max(g[i][j],f[i][j]);
//			f[i][j]=max(f[i+1][j-1],f[i][j]);}}ll ans=0;for(int i=1;i<=n;i++){ll tmp=0;for(int j=1;j<=2*n;j++) tmp^=f[i][j]*j;ans^=tmp+i;}cout << ans;
}