Square-free division
因为是判断是否有两个数乘起来为完全平方数是,所以可以先把数里的完全平方项,这样判断是否有两个数乘起来为完全平方数可以直接判断是否有两个相同的数。又因为一次修改可以改为任何数,所以如果存在 \(x\) 个数相同,我们需要修改的次数为 \(x-1\)。
可以想到 dp,令 \(f_{i,j}\) 表示 \([1,i]\) 用了 \(x\) 次修改能分成的最小段数,枚举转移点 \(k\),假定区间 \([k+1,i]\) 用了 \(cnt\) 次修改,可以从 \(f_{k,j-cnt}\) 转移,复杂度 \(O(n^2k)\)。但我们发现其实没这么复杂,对于一个 \(i,cnt\) 能转移过来的点其实是唯一的,因为限制修改次数肯定是转移尽量大的一个区间,可以使用双指针预处理转移点。复杂度 \(O(nk^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,K=21,V=1e7+10;
int n,m,a[N],f[N][K],vis[V],pre[N][K];
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
read(a[i]);
int tmp=a[i];
a[i]=1;
for(int j=2;j*j<=tmp;j++){
int cnt=0;
while(tmp%j==0){
cnt++;
tmp/=j;
}
if(cnt&1){
a[i]=a[i]*j;
}
}
if(tmp){
a[i]*=tmp;
}
}
for(int i=0;i<=m;i++){
int cnt=0;
for(int j=1,k=1;j<=n;j++){
if(vis[a[j]]){
cnt++;
}
vis[a[j]]++;
while(cnt>i){
vis[a[k]]--;
if(vis[a[k]]){
cnt--;
}
k++;
}
pre[j][i]=k-1;
}
for(int j=1;j<=n;j++){
vis[a[j]]=0;
}
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=j;k++){
f[i][j]=min(f[i][j],f[pre[i][k]][j-k]+1);
}
}
}
int ans=inf;
for(int i=0;i<=m;i++){
ans=min(ans,f[n][i]);
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
Christmas Game
容易发现这也是一个 Nim 游戏,因为能跳偶数步的石子是没有意义的,两个人轮流跳这些石子不能带来任何贡献,只有跳奇数步的能够带来贡献,这样就转化为了最原始的取石子的形式了。
但我们还是需要计算对于每一个点跳奇数步的石子堆的数量的异或和,这显然不能让你 \(n^2\) 暴力找。还是只能换根,令 \(f_{u,0/1}\) 表示点 \(u\) 子树内跳偶数步/奇数步的石子堆数量的异或和。但我们发现这个不好换根,因为根移动一步并不是所有贡献都改变,所以再加一维状态,令 \(f_{u,i,0/1}\) 表示点 \(u\) 子树内满足 \(dep\bmod k=i\) 的点跳偶数步/奇数步的石子堆数量的异或和,剩下的就非常简单了。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10,Lg=20;
int n,m,a[N],f[N][Lg+5][2];
vector<int>e[N];
int tmp[25][2];
void work(int u,int fa){
f[u][0][0]=a[u];
for(auto v:e[u]){
if(v==fa){
continue;
}
work(v,u);
for(int j=0;j<m;j++){
for(int k=0;k<=1;k++){
f[u][(j+1)%m][k^((j+1)/m)]^=f[v][j][k];
}
}
}
}
void dfs(int u,int fa){
if(u!=1){
for(int j=0;j<m;j++){
for(int k=0;k<=1;k++){
tmp[j][k]=f[fa][j][k];
}
}
for(int j=0;j<m;j++){
for(int k=0;k<=1;k++){
tmp[(j+1)%m][k^((j+1)/m)]^=f[u][j][k];
}
}
for(int j=0;j<m;j++){
for(int k=0;k<=1;k++){
f[u][(j+1)%m][k^((j+1)/m)]^=tmp[j][k];
}
}
}
for(auto v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
}
}
void solve(){
read(n),read(m);
for(int i=1,u,v;i<n;i++){
read(u),read(v);
e[u].pb(v);
e[v].pb(u);
}
for(int i=1;i<=n;i++){
read(a[i]);
}
work(1,0);
dfs(1,0);
for(int i=1;i<=n;i++){
int ans=0;
for(int j=0;j<m;j++){
ans^=f[i][j][1];
}
if(ans){
write_space(1);
}
else{
write_space(0);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
「JOI 2017 Final」准高速电车
所有的换乘肯定只有从快的换乘到慢的。我们将快车的两个站之间看作一段,显然这一段可以分为不经过准快车站,经过一个准快车站,经过两个,经过三个,……,不可到这若干段。为了使每一段都尽量长,我们肯定将准快车站建在上一段终点的后面一站。用优先队列维护每一个大段的当前的第一个小段包含的站的数量,优先选择包含站数量多的小段。
因为优先队列中的段的数量不超过 \(m\),总复杂度 \(O(k\log m)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int __int128
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
int n,m,k,a,b,c,t;
struct node{
int l,r,t;
friend bool operator <(const node &now,const node &rhs){
int cnt1=(now.t-c)/a+1,tot1=now.r-now.l+1;
int cnt2=(rhs.t-c)/a+1,tot2=rhs.r-rhs.l+1;
return min(cnt1,tot1)<min(cnt2,tot2);
}
};
priority_queue<node>q;
void solve(){
read(n),read(m),read(k);
k-=m;
read(a),read(b),read(c);
read(t);
int lst=1,lst_t=t;
int ans=1;
while(!q.empty()){
q.pop();
}
for(int i=1,x;i<=m+1;i++){
if(i!=m+1){
read(x);
}
else{
x=n;
}
if(x==lst){
continue;
}
int cnt=x-lst-1,tot=lst_t/a;
if(lst_t<=0){
continue;
}
if(i!=m+1&&t>=b*(x-1)){
ans++;
}
if(cnt<=tot){
ans+=cnt;
}
else{
ans+=tot;
q.push(node{lst+tot+1,i==m+1?x:x-1,lst_t-c*tot});
// cerr<<lst+tot+1<<' '<<x-1<<endl;
}
// cerr<<x<<' '<<cnt<<' '<<tot<<' '<<ans<<endl;
lst_t=t-b*(x-1);
lst=x;
// cerr<<x<<' '<<ans<<endl;
}
for(int i=1;i<=k;i++){
if(q.empty()){
break;
}
node x;
while(q.size()){
x=q.top();
q.pop();
if(x.t<c||x.l>x.r){
continue;
}
else{
break;
}
}
if(x.t<c){
break;
}
int cnt=(x.t-c)/a+1,tot=x.r-x.l+1;
if(tot<=cnt){
ans+=tot;
}
else{
ans+=cnt;
x.l=x.l+cnt;
x.t=x.t-cnt*c;
q.push(x);
}
}
write_endl(ans-1);
}
signed main(){
#ifdef luoshen
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#else
// freopen("lunae.in","r",stdin);
// freopen("lunae.out","w",stdout);
#endif
int id,t=1;
while(t--){
solve();
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
Sonya and Problem Wihtout a Legend
Slope trick经典题。
将 \(a_i\rightarrow a_i-i\),这样就由严格递增变成了非严格递增。有一个思路,用一个优先队列维护操作后序列的最大值,对于一个新的数 \(x\),将其放入堆中,如果它是最大值不管,否则将最大值改为 \(x\) 放入堆中。如果修改后最大值 \(z>x\),令 \(z'\) 为修改完所有数之后 \(z\) 的值,若 \(z'<x\),不影响;若 \(z>x',\)此时我们可以把两个数全修改为 \(z'\),答案并不会变化。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
priority_queue<int>q;
int n,x;
ll ans;
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(x);
x-=i;
q.push(x);
if(x<q.top()){
ans+=q.top()-x;
q.pop();
q.push(x);
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
「JOISC 2016 Day 3」回转寿司
对于一个操作,可以发现就是将 \(x\) 和区间中的数放在一起,答案就是这些数中的最大值。也就是我们其实并不是很关心每个位置的数是多少,只关心这些数中的最大值。
考虑分块,用两个堆维护,一个维护块内数的最大值,一个维护到加入到整个块中的数的最小值。对于整块很好处理,直接将数放入大根堆中,取出堆顶就是答案。对于一个散块,显然每个数的权值就是可能修改它的值与它自己原本权值中的最小值,利用开始的小根堆暴力维护出每个数,再算答案,并重新维护大根堆。复杂度 \(O(n\sqrt{n}\log n)\),时限给得很大,完全能过。
[THUPC 2023 决赛] 先人类的人类选别
和上面的题很像,但是数据范围完全不支持分块。这道题唯一好的一点是修改全都是整个区间。将区间 \([l,r]\) 的答案拆成前缀 \(r\) 的答案减前缀 \(l-1\) 的答案,假定加了 \(x\) 个数,那么前缀 \(i\) 的答案就是加的数的和加原来的数的和再减去这些数里的前 \(x\) 小的数的和。
这是可以用权值线段树维护的。原来的数的和可以用可持久化线段树,对于每个位置 \(i\) 建一个版本,维护前 \(i\) 个数的和,再用一个动态开点线段树维护加的数的和,求两棵树并起来的前 \(k\) 小的和可以使用线段树二分完成。复杂度 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10,Lg=40;
int n,m,a[N],suf[N],idx;
namespace Seg_Tree{
struct node{
int ch[2],sum,siz;
}tr[N*Lg];
#define ls(p) tr[p].ch[0]
#define rs(p) tr[p].ch[1]
void change(int &p,int pre,int l,int r,int val){
p=++idx;
tr[p]=tr[pre];
tr[p].siz++;
tr[p].sum+=val;
if(l==r){
return;
}
int mid=(l+r)>>1;
if(val<=mid){
change(ls(p),ls(pre),l,mid,val);
}
else{
change(rs(p),rs(pre),mid+1,r,val);
}
}
void update(int &p,int l,int r,int val){
if(!p){
p=++idx;
}
tr[p].siz++;
tr[p].sum+=val;
if(l==r){
return;
}
int mid=(l+r)>>1;
if(val<=mid){
update(ls(p),l,mid,val);
}
else{
update(rs(p),mid+1,r,val);
}
}
int query(int p,int q,int l,int r,int k){
if(l==r){
return k*l;
}
int siz=tr[ls(p)].siz+tr[ls(q)].siz;
int mid=(l+r)>>1;
if(siz>=k){
return query(ls(p),ls(q),l,mid,k);
}
else{
return tr[ls(p)].sum+tr[ls(q)].sum+query(rs(p),rs(q),mid+1,r,k-siz);
}
}
}
int rt[N];
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
read(a[i]);
suf[i]=suf[i-1]+a[i];
}
for(int i=1;i<=n;i++){
Seg_Tree::change(rt[i],rt[i-1],1,n,a[i]);
}
int sum=0;
for(int i=1;i<=m;i++){
int val,l,r;
read(val),read(l),read(r);
sum+=val;
Seg_Tree::update(rt[n+1],1,n,val);
int add=suf[r]+sum-Seg_Tree::query(rt[r],rt[n+1],1,n,i);
int del=suf[l-1]+sum-Seg_Tree::query(rt[l-1],rt[n+1],1,n,i);
write_endl(add-del);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[POI2012] STU-Well
先忽略 \(a_k=0\) 的条件,只限制差的绝对值最小怎么做。考虑二分,令 \(x\) 为二分出来的值,如果 \(a_i\) 已经确定权值,且 \(a_{i+1}>a_i+x\),显然 \(a_{i+1}\) 应当修改为 \(a_i+x\)。再反向做一遍,就可以确定每个数最后的权值。
假定我们钦定 \(a_k=0\),那么 \(\forall i<k\),\(a_i\le x\times(k-i)\);\(\forall i>k\),\(a_i\le x\times (i-k)\)。显然限制的是一个区间,直接双指针扫一遍就可以找到是否存在 \(k\) 满足操作次数不超过 \(m\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10;
int n,m,a[N],b[N],suf[N];
int check(int x){
int cnt=m;
for(int i=1;i<=n;i++){
b[i]=a[i];
}
for(int i=n-1;i;i--){
b[i]=min(b[i],b[i+1]+x);
}
for(int i=2;i<=n;i++){
b[i]=min(b[i],b[i-1]+x);
}
for(int i=1;i<=n;i++){
suf[i]=suf[i-1]+b[i];
cnt-=a[i]-b[i];
}
int l=1,r=1;
for(int i=1;i<=n;i++){
while(b[l]<(i-l)*x){
l++;
}
while(r<n&&b[r+1]>=(r-i+1)*x){
r++;
}
if(suf[r]-suf[l-1]-x*((i-l+1)*(i-l)/2+(r-i+1)*(r-i)/2)<=cnt){
return i;
}
}
return 0;
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
read(a[i]);
}
int l=0,r=inf,ans=inf,pos=0;
while(l<=r){
int mid=(l+r)>>1;
int val=check(mid);
if(val){
ans=mid;
pos=val;
r=mid-1;
}
else{
l=mid+1;
}
}
write_space(pos),write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}