10.19noip模拟赛一
T1 序列
算法:dp
观察到所有数 \(\mod 3\),所以只有三种取值\(\{0,1,2\}\),所以想要将原序列模 \(3\) 以后做。经过简单的运算发现，所有数模 \(3\) 以后做是等价的，所以可以转化。然后考虑题求得很想最长上升子序列，而最长上升子序列有一种 \(O(nlogn)\)做法，即记录前一个数是几的最大值，本题很类似，与前一个数和前一差值有关，所以定义 \(f[i][j]\) 表示前一个数是 \(i\),差值为j最大距离。直接更新即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],res[10],dp[10][10];
int md(int x)
{
if(x>=0)return x%3;
else return x=-2*x,x%3;
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=md(a[i]);
}
dp[a[1]][0]=1;
for(int i=2;i<=n;i++)
{
for(int las=0;las<=2;las++)
{
int c=md(a[i]-las);
for(int cj=c;cj>=0;cj--)res[c]=max(res[c],dp[las][cj]+1);
}
for(int c=0;c<=2;c++)
{
dp[a[i]][c]=max(dp[a[i]][c],res[c]);
res[c]=0;
}
dp[a[i]][0]=max(dp[a[i]][0],1);
}
int ans=min(2,n);
for(int i=0;i<=2;i++)
for(int j=0;j<=2;j++)
ans=max(ans,dp[i][j]);
cout<<ans<<'\n';
return 0;
}
反思:
考场上写出来了，算是理解到了的。\(dp\) 状态的设计一定是有转移中有用的信息决定的。
T2组队参赛
原题链接
算法：dp
先有一些性质，已知\(a_i\)越小越容易满足，所以先按\(a_i\)排序，考虑做出最多题的某一种方案一定是满足前缀。所以设 \(f[i]\) 表示用前 \(i\) 个数满足前 \(i\) 个人可以分得最大组数（不考虑后面的数）。有 \(f[i]=max_{j<=i-a[i]}(f[j])+1\),所以总组数为\(n+f[i]-i\),但如果i<a[i]就无意义了，只能用后面的数来满足，所以 \(f[i]=0\),总组数为 \(n-a[i]+1\)。所以分情况转移即可。
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,q,a[N],b[N],f[N],ans[N],g[N];
int main()
{
// freopen("xcpc.in","r",stdin);
// freopen("xcpc.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
if(a[i]<=i)f[i]=f[i-a[i]]+1,g[i]=n-i+f[i];
else f[i]=0,g[i]=n-a[i]+1;
f[i]=max(f[i-1],f[i]);
ans[g[i]]=i;
}
for(int i=n;i>=1;i--)ans[i]=max(ans[i+1],ans[i]);
cin>>q;
for(int i=1;i<=q;i++)
{
int x;cin>>x;
cout<<ans[x]<<'\n';
}
return 0;
}
反思：
没有想到dp方面，主要是连第一步的转化都没想到，所以要多挖掘题目性质，简化题目。
T3游戏（填坑）
叫游戏的题就没做出来过！！！
T4交换比特
还是要先推性质。考虑 \(n=2\) 的情况，只有四种可能\(2112,1221,1212,2121\) 前两种转化为\(1122,2211\) 都可以，但后两种则只能分别转化为 \(1122\) 和 \(2211\) 来满足最小步数,所以
形式化的来说，如果 \(l[i]<l[j]\) 并且 \(r[i]<r[j]\) 则 \(i\) 一定在 \(j\) 以前（\(l[i]\) 表示i第一次出现，\(r[i]\) 表示第二次出现）。所以我们可以从 \(i\) 向 \(j\) 连边，跑topu即可。但考虑连边的最坏时间复杂度为 \(O(n^2)\),所以要优化建图。因为连边的限制是二维偏序，所以用cdq优化建图。
#include <bits/stdc++.h>
using namespace std;
const int N=2e7+10;
int n,a[N],tot,cnt,nxt[N],hd[N],go[N],in[N],xd[N],l[N],R[N];
struct node
{
int id,ll,rr;
}b[N],jz[N];
bool cmp(node x,node y)
{
return x.ll<y.ll;
}
void add(int x,int y)
{
nxt[++tot]=hd[x];go[tot]=y;in[y]++;hd[x]=tot;
return;
}
void solve(int l,int r)
{
if(l==r)return ;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
int jcnt=cnt;
for(int i=mid+1;i<=r;i++)
{
xd[i]=++cnt;//右边的每个点建虚点出来
add(cnt,b[i].id); //虚点向原点连边
}
for(int i=mid+1;i<r;i++)add(xd[i],xd[i+1]);//虚点之间连边，前缀优化。
int x=l,j=mid+1,i=l;bool flag=0;
for(;i<=mid;i++)
{
while(j<r&&b[j].rr<b[i].rr)jz[x++]=b[j],j++;
if(flag==0&&j==r&&b[i].rr>b[j].rr)jz[x++]=b[j],flag=1;
if(b[i].rr<b[j].rr)add(b[i].id,xd[j]);//左边的点向右边的第一个r[j]>r[i]的点的虚点连边
jz[x++]=b[i];
}
if(j<=r)jz[x++]=b[j];
for(int i=l;i<=r;i++)b[i]=jz[i];
return;
}
queue<int> q;
priority_queue<int,vector<int>,greater<int> > qx;
int main()
{
freopen("swap.in","r",stdin);
freopen("swap.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=2*n;i++)
{
cin>>a[i];
if(l[a[i]]==0)l[a[i]]=i;
else R[a[i]]=i;
}
for(int i=1;i<=n;i++)
{
b[i].id=i;b[i].ll=l[i];b[i].rr=R[i];
}
cnt=n;
sort(b+1,b+n+1,cmp);
solve(1,n);
for(int i=1;i<=n;i++)
if(!in[i])qx.push(i);
for(int i=n+1;i<=cnt;i++)
if(!in[i])q.push(i);
while(!q.empty()||!qx.empty())
{
int u;
if(!q.empty())
{
u=q.front();q.pop();
}
else
{
u=qx.top();qx.pop();
cout<<u<<" "<<u<<" ";
}
for(int i=hd[u];i;i=nxt[i])
{
int v=go[i];
in[v]--;
if(in[v]==0)
{
if(v<=n)qx.push(v);
else q.push(v);
}
}
}
return 0;
}
反思:性质没推出来，虽然即使推出来也不会用优化建图，改题理解的还是比较深刻，建图优化一定是根据性质选择。
10.21noip模拟赛二
T1 致敬传奇捆绑测试题目
算法：贪心，打表
打表找规律题，显然最优方案是\(3,1,2,4,5...\)，除了前三位，性质很优美，全部异或在一起，偶数一定是会$4\oplus6\oplus8\oplus10.. $所以显然有规律，直接打表，就没有然后了。（也可以拆位做，或数学推导）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,ans,k,jg[10]={0,0,6,4,0,0,2,0};
int main()
{
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
if(n==1||n==2){
cout<<"2"<<'\n';
return 0;
}
if(n==3){
cout<<"3"<<'\n';
return 0;
}
n-=4;
int x=n%8;
if(x!=0&&x!=4&&x!=1&&x!=5)cout<<jg[x]<<'\n';
else if(x==0||x==1) cout<<2ll*(n-x+5)<<'\n';
else if(x==4||x==5) cout<<2ll*(n-x+11)<<'\n';
return 0;
}
反思：数学推导一直推不出来，一个半小时才打表发现规律，下次根据题目难度选推导或打表。
T2 串串
算法：dp
因为要求的答案为极差，直接dp不好做，所以需要钦定最大值和最小值，一共只有26个字母，所以定义 \(dp[i][j]\) 表示 \(i\) 的数量最多,\(j\) 的数量最少的最大权值差。但考虑转移出的结果有可能根本没选 \(j\),所以加一维限制表示是否选了 \(j\)。时间复杂度为\(O(26^2n)\),但考虑只有等于 \(i\) 或 等于 \(j\) 时对 \(dp[i][j][0/1]\) 有改变。所以只用 \(O(52n)\) 即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,ans,col[30],f[30][30][2];
char s[N];
int main()
{
freopen("range.in","r",stdin);
freopen("range.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>s;
for(int i=0;i<26;i++)
for(int j=0;j<26;j++)
f[i][j][1]=-2;
for(int i=0;i<n;i++)
{
int x=s[i]-'a';
for(int j=0;j<26;j++)
{
if(j==x)continue;
f[x][j][0]++;
if(f[x][j][1]!=-2)f[x][j][1]++;
f[j][x][1]=max(max(f[j][x][1],f[j][x][0])-1,-1);//只选一个x,为-1,对f[x][j]有用。
f[j][x][0]=0;
ans=max(ans,max(f[j][x][1],f[x][j][1]));
}
}
cout<<ans<<'\n';
return 0;
}
T3计算几何
还要先推性质，可能造成贡献的只有左边或右边最近的高度小于当前点的点，证明比较简单，如果我们求得结果为 \((i,j)\) 且不是刚才所得类型，则 \((i,l[j])\) 一定更优( \(l[j]\) 表示 \(j\) 左边最近的高度小于当前点的点)，因为 \(x[l[j]]-x[i]<x[j]-x[i],w[i]+w[l[j]]<w[i]+w[j]\) 结果所以单调栈求出来。按横坐标排序，反过来的树状数组维护一下即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=3e5+10;
#define int long long
int n,qq,sh[M],h[M],w[M],ans[M],top,st[M];
vector <int> q[M];
struct node
{
int l,id;
};
vector<node> qu[M];
int lowbit(int x){return x&-x;}
void modify(int x,int zhi)
{
while(x)
{
sh[x]=min(sh[x],zhi);
x-=lowbit(x);
}
}
int query(int x)
{
int res=9e18;
while(x<=n)
{
res=min(res,sh[x]);
x+=lowbit(x);
}
return res;
}
signed main()
{
// freopen("geo.in","r",stdin);
// freopen("geo.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>qq;
for(int i=1;i<=n;i++)cin>>h[i]>>w[i],sh[i]=9e18;
for(int i=1;i<=n;i++)
{
while(top&&w[st[top]]>w[i])top--;
if(top)q[i].push_back(st[top]);
st[++top]=i;
}
top=0;
for(int i=n;i>=1;i--)
{
while(top&&w[st[top]]>w[i])top--;
if(top)q[st[top]].push_back(i);
st[++top]=i;
}
for(int i=1;i<=qq;i++)
{
int l,r;cin>>l>>r;
qu[r].push_back((node){l,i});
}
for(int i=1;i<=n;i++)
{
for(auto u:q[i])
modify(u,1ll*(h[i]-h[u])*(w[i]+w[u]));
for(auto u:qu[i])
ans[u.id]=query(u.l);
}
for(int i=1;i<=qq;i++)cout<<ans[i]<<'\n';
return 0;
}
T4消消乐(待填)
10.22noip模拟赛三
T1 链链链
算法：贪心
贪心一：正向思考，最大值一定会跟其它点分开，将它与先分开一定是最优的，所以每次找最大值即可。（st表）
贪心二：反向思考，合并时先将小的合并到左右两边的大值上一定最优，每次选代价小的即可。（链表）
还可以 \(o(n)\) dp。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
int c,t,n;
ll ans;
struct node
{
int id;ll zhi;
}a[N];
bool cmp(node x,node y)
{
return x.zhi<y.zhi;
}
struct lb
{
int nxt,pre;
ll mx,zhi;
}b[N];
int main()
{
freopen("chain.in","r",stdin);
freopen("chain.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>c>>t;
while(t--)
{
cin>>n;ans=0;
for(int i=1;i<=n;i++)cin>>a[i].zhi,a[i].id=i;
sort(a+1,a+n+1,cmp);
b[0].mx=0;
for(int i=1;i<=n;i++)
{
b[a[i].id].zhi=a[i].zhi;
if(a[i].zhi==a[i-1].zhi)b[a[i].id].mx=b[a[i-1].id].mx;
else b[a[i].id].mx=b[a[i-1].id].mx+1;
}
for(int i=1;i<=n;i++)b[i].nxt=i+1,b[i].pre=i-1;
b[0].nxt=1,b[n+1].pre=n;
b[0].mx=b[n+1].mx=b[0].zhi=b[n+1].zhi=0x3f3f3f3f;
for(int i=1;i<n;i++)
{
int cur=a[i].id;
ll zb=abs(b[b[cur].pre].zhi-b[cur].zhi),yb=abs(b[b[cur].nxt].zhi-b[cur].zhi);
ans+=min(zb,yb);
b[b[cur].pre].nxt=b[cur].nxt;
b[b[cur].nxt].pre=b[cur].pre;
}
cout<<ans<<'\n';
}
return 0;
}
反思:只会第一题，还自己给自己增加了一个 \(n\) 的复杂度，挂了30。写题前应该先理清思路，在可能的范围内选择最优最简单的做法