付费网站推广,上海出啥大事了今天,怎么查询最新网站,网站一直没有收录前言
终于出成绩了我可以写博客辣#xff0c;官方数据还没出就先放洛谷的题目链接了。 正题 T1-廊桥分配
https://www.luogu.com.cn/problem/P7913
题目大意
有m1m_1m1种一类飞机#xff0c;m2m_2m2种二类飞机#xff0c;每个飞机有一个占用时间的区间。要给两类飞机…前言
终于出成绩了我可以写博客辣官方数据还没出就先放洛谷的题目链接了。 正题 T1-廊桥分配
https://www.luogu.com.cn/problem/P7913
题目大意
有m1m_1m1种一类飞机m2m_2m2种二类飞机每个飞机有一个占用时间的区间。要给两类飞机分配恰好nnn个廊桥。 如果对于一类飞机当它来到时如果有空的它这一类的廊桥就会分配给他。 求最多能容纳多少飞机。
1≤n≤105,1≤m1m2≤1051\leq n\leq 10^5,1\leq m_1m_2\leq 10^51≤n≤105,1≤m1m2≤105
解题思路
因为飞机的策略就是能停就停我们可以考虑贪心策略。 先考虑单类的飞机假设分配的廊桥为kkk当一辆飞机不能进入当且仅当现在kkk个廊桥已经被霸占了此时如果需要停靠这俩飞机就需要新开一个廊桥。 我们可以设有无数个廊桥然后我们优先分配编号小的廊桥然后最后如果有kkk个廊桥时答案就是在1∼k1\sim k1∼k的廊桥排列的飞机数。 具体的做法对于两类各做一次用一个优先队列维护现在所有被霸占的廊桥的恢复时间然后用一个set维护现在空余的廊桥编号就可以了。
时间复杂度O(nlogn)O(n\log n)O(nlogn)
code
#includecstdio
#includecstring
#includealgorithm
#includeset
#includequeue
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1e510;
struct node{int l,r;
}a[N];
int n,m,f[N],g[N];setint s;
priority_queuepairint,int q;
bool cmp(node x,node y)
{return x.ly.l;}
int main()
{int pm;scanf(%d%d%d,n,m,pm);for(int i1;imax(n,max(m,pm));i)s.insert(i);for(int i1;im;i)scanf(%d%d,a[i].l,a[i].r);sort(a1,a1m,cmp);for(int i1;im;i){while(!q.empty()-q.top().firsta[i].l)s.insert(q.top().second),q.pop();int x*s.begin();f[x];s.erase(x);q.push(mp(-a[i].r,x));}while(!q.empty())s.insert(q.top().second),q.pop();for(int i1;in;i)f[i]f[i-1];mpm;for(int i1;im;i)scanf(%d%d,a[i].l,a[i].r);sort(a1,a1m,cmp);for(int i1;im;i){while(!q.empty()-q.top().firsta[i].l)s.insert(q.top().second),q.pop();int x*s.begin();g[x];s.erase(x);q.push(mp(-a[i].r,x));}while(!q.empty())s.insert(q.top().second),q.pop();for(int i1;in;i)g[i]g[i-1];int ans0;for(int i0;in;i)ansmax(ans,f[i]g[n-i]);printf(%d\n,ans);return 0;
}T2-括号序列
https://www.luogu.com.cn/problem/P7914
题目大意
一个合格的括号序被定义为 然后给出带∗,(,),?*,(,),?∗,(,),?的字符串然后求有多少种把???切换成(,),∗(,),*(,),∗的方案使得是一个合法的括号序。 1≤k≤n≤5001\leq k\leq n\leq 5001≤k≤n≤500
解题思路
开始考虑一个一个填发现不行。 然后这个复杂度考虑区间dpdpdp设fl,rf_{l,r}fl,r表示区间l∼rl\sim rl∼r合法的方案。 然后考虑怎么转移先维护一个sl,rs_{l,r}sl,r表示l∼rl\sim rl∼r是否能够凑成一个长度不超过kkk的全∗*∗序列。 对于第111种和第333种情况先看下l,rl,rl,r是否能是′(′(′(′和′)′)′)′的形式然后第一种情况就直接加sl1,r−1fl1,r−1s_{l1,r-1}f_{l1,r-1}sl1,r−1fl1,r−1对应S/AS/AS/A第三种我们可以枚举k∈[l1,r−1)k\in[l1,r-1)k∈[l1,r−1)然后转移fl1,k×sk1,rsl1,k×fk1,rf_{l1,k}\times s_{k1,r}s_{l1,k}\times f_{k1,r}fl1,k×sk1,rsl1,k×fk1,r对应了AS/SAAS/SAAS/SA就好了。 第222种情况比较麻烦我们需要枚举一个l≤LR≤rl\leq LR\leq rl≤LR≤r然后中间填SSS就是fl,L×fR,r×sL1,R−1f_{l,L}\times f_{R,r}\times s_{L1,R-1}fl,L×fR,r×sL1,R−1。但是这个枚举比较慢因为对于一个rrr满足sl,r1s_{l,r}1sl,r1的lll肯定是一个到rrr的区间并且rrr向右移动时这个区间也向右移动所以可以使用一个前缀和优化。
发现这样还是过不了样例问题出在如果存在ASASAASASAASASA的情况此时会被统计两次∣ASA∣SA|ASA|SA∣ASA∣SA和AS∣ASA∣AS|ASA|AS∣ASA∣各一次更多的同理所以我们可以设gl,rg_{l,r}gl,r表示不带情况二时的合法方案然后在后面转移就好了。
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N510,P1e97;
ll n,k,f[N][N],g[N][N],S[N][N];char s[N];
signed main()
{scanf(%lld%lld,n,k);scanf(%s,s1);for(ll i1;in;i){S[i][i-1]1;for(ll ji;jmin(n,ik-1);j){S[i][j]S[i][j-1](s[j]?||s[j]*);if(!S[i][j])break;}}for(ll len2;lenn;len)for(ll l1;ln-len1;l){ll rllen-1;if((s[l]?||s[l]()(s[r]?||s[r]))){(f[l][r]S[l1][r-1]f[l1][r-1])%P;for(ll kl1;kr-1;k)(f[l][r]f[l1][k]*S[k1][r-1]f[k1][r-1]*S[l1][k])%P;}ll sum0,zl;g[l][r]f[l][r];for(ll kl;kr;k){(sumf[l][k])%P;while(!S[z1][k])(sum-f[l][z])%P,z;(f[l][r]g[k1][r]*sum%P)%P;}}printf(%lld\n,(f[1][n]P)%P);return 0;
}T3-回文
https://www.luogu.com.cn/problem/P7915
题目大意
有一个长度为2n2n2n的序列aaa保证1∼n1\sim n1∼n都各出现了两次你有两种操作
将aaa的开头添加到序列bbb的末尾并在aaa移除。将aaa的末尾添加到序列bbb的末尾并在aaa移除。
一操作为LLL二操作为RRR要求使得最终bbb回文的情况下操作序列的字典序最小。
1≤T≤100,∑n≤5×1051\leq T\leq 100,\sum n\leq 5\times 10^51≤T≤100,∑n≤5×105
解题思路
显然第一个丢进bbb的肯定是第一个或者最后一个我们先假设是第一个且数字为xxx那么最后被丢进去的肯定是另一个xxx。
然后我们可以从这个xxx的位置开始作为一个区间然后开始每次你丢进去的下一个数都必须在这个区间的左右然后再用这个区间再扩展丢进去的数的另一个的对应位置。
但是这样暴力搜丢左边还是右边是2n2^n2n的显然不行但是我们发现假设如果一个情况左右都能丢在字典序最小的情况下我们肯定是先丢左边的而此时丢了之后不会导致右边不能丢了所以此时丢左边肯定是最优的。
所以其实这样搜是O(n)O(n)O(n)的时间复杂度O(∑n)O(\sum n)O(∑n)。
code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
int T,n,flag,a[N];char v[N];
void dfs(int d,int l,int r,int L,int R){if(lLrR){flag1;for(int i1;i2*n;i)putchar(v[i]);putchar(\n);return;}if(dn)return;if(Ll(a[L]a[l]Ll||a[L]a[r]rR)){v[d]L;if(a[L]a[l]Ll)v[2*n-d1]L,dfs(d1,l-1,r,L1,R);else v[2*n-d1]R,dfs(d1,l,r1,L1,R);}else if(rR(a[R]a[l]Ll||a[R]a[r]rR)){v[d]R;if(a[R]a[l]Ll)v[2*n-d1]L,dfs(d1,l-1,r,L,R-1);else v[2*n-d1]R,dfs(d1,l,r1,L,R-1);}return;
}
int main()
{scanf(%d,T);while(T--){scanf(%d,n);v[2*n]L;flag0;for(int i1;i2*n;i)scanf(%d,a[i]);for(int i2;i2*n;i)if(a[i]a[1]){v[1]L;dfs(2,i-1,i1,2,2*n);break;}if(flag)continue;for(int i1;i2*n;i)if(a[i]a[2*n]){v[1]R;dfs(2,i-1,i1,1,2*n-1);break;}if(flag)continue;puts(-1);}return 0;
}T4-交通规划
https://www.luogu.com.cn/problem/P7916
题目大意
有一个nnn条水平线和mmm条垂直线交叉形成n×mn\times mn×m个格点的图把所有的边按照顺时针排序如图。 每个格点之间有边权。 TTT次询问每次给出线外的kkk个额外点的位置颜色黑白和连接线内边界格点的边权。
要求给网格上的所有点染色要求使得两端颜色不同的边权值和最小。
1≤T≤50,∑k≤50,2≤n,m≤5001\leq T\leq 50,\sum k\leq 50,2\leq n,m\leq 5001≤T≤50,∑k≤50,2≤n,m≤500。
解题思路
黑白染色求最小的权值其实就是为最小割然后平面图最小割是可以转换成对偶图的最短路的。
显然的对于k2k2k2的部分分就是直接求黑色额外点如果颜色都相同显然答案为000左右的对偶点在对偶图上的最短路。
对于kkk更大的情况我们具体分析一下对于下图的情况为了好看用了红蓝代替黑白 我们有两种割法绿/黄 发现其实可以写成四个点相互匹配的过程由于产生交叉的肯定不优通过改变匹配方式使得交叉部分消去所以匹配的贡献可以直接写成最短路。
然后考虑如何找到优的匹配方案我们可以把顺时针的和逆时针的匹配因为如果顺顺-逆逆的匹配的话肯定会产生交叉。虽然这样匹配也可能产生交叉但是因为权值不优所以不会影响答案
然后就是一个二分图最大权值匹配的问题了写个费用流就可以了。
虽然再利用交叉性质做环形区间dpdpdp也能过但是我不会/kk
code
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includevector
#includequeue
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N510,MN*N,K110;
struct edge{ll to,next,w;
}a[M2];
struct node{ll w,p,t;
}q[K];
ll n,m,T,tot,ls[M],f[M],wz[N2];
vectorint A,B;bool v[M];
priority_queuepairll,ll qt;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
struct Netflow{struct node{ll to,next,w,c;}a[K*K*2];ll tot1,s1,t2,ans,ls[K],f[K],mf[K],pre[K];bool v[K];priority_queueint q;void clr(){tot1;ans0;memset(ls,0,sizeof(ls));return;}void addl(ll x,ll y,ll w,ll c){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].cc;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;a[tot].c-c;return;}bool SPFA(){memset(f,0x3f,sizeof(f));q.push(s);f[s]0;v[s]1;mf[s]1e9;while(!q.empty()){ll xq.top();q.pop();v[x]0;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(a[i].wf[x]a[i].cf[y]){f[y]f[x]a[i].c;pre[y]i;mf[y]min(mf[x],a[i].w);if(!v[y])q.push(y),v[y]1;}}}return (f[t]!f[0]);}void Updata(){ll xt;ansmf[t]*f[t];while(x!s){a[pre[x]].w-mf[t];a[pre[x]^1].wmf[t];xa[pre[x]^1].to;}return;}ll GetAns(){while(SPFA())Updata();return ans;}
}Nt;
ll p(ll x,ll y)
{return x*(m1)y;}
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].ww;return;
}
void dij(ll s){memset(f,0x3f,sizeof(f));memset(v,0,sizeof(v));f[s]0;qt.push(mp(0,s));while(!qt.empty()){ll xqt.top().second;qt.pop();if(v[x])continue;v[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;qt.push(mp(-f[y],y));}}}return;
}
ll getp(ll x,ll f){if(xm)return p(0,xf);if(xmn)return p(x-mf,m);if(x2*mn)return p(n,m-(x-m-nf));return p(n-(x-2*m-nf),0);
}
bool cmp(node x,node y)
{return x.py.p;}
signed main()
{nread();mread();Tread();for(ll i1;in;i)for(ll j1;jm;j){ll wread();addl(p(i,j-1),p(i,j),w);}for(ll i1;in;i)for(ll j1;jm;j){ll wread();addl(p(i-1,j),p(i,j),w);}for(ll i1;im;i)addl(p(0,i-1),p(0,i),0),wz[i]tot;for(ll i1;in;i)addl(p(i-1,m),p(i,m),0),wz[im]tot;for(ll i1;im;i)addl(p(n,m-i1),p(n,m-i),0),wz[inm]tot;for(ll i1;in;i)addl(p(n-i1,0),p(n-i,0),0),wz[in2*m]tot;while(T--){ll kread();Nt.clr();A.clear();B.clear();for(ll i1;ik;i){q[i].wread();q[i].pread();q[i].tread();a[wz[q[i].p]].wa[wz[q[i].p]-1].wq[i].w;}sort(q1,q1k,cmp);q[0]q[k];q[k1]q[1];for(ll i1;ik;i)if(q[i].t1q[i-1].t0)A.push_back(getp(q[i].p,-1));for(ll i1;ik;i)if(q[i].t1q[i1].t0)B.push_back(getp(q[i].p,0));for(ll i0;iA.size();i){Nt.addl(1,3i,1,0);dij(A[i]);for(ll j0;jB.size();j)Nt.addl(3i,3A.size()j,1,f[B[j]]);}for(ll i0;iB.size();i)Nt.addl(3A.size()i,2,1,0);printf(%lld\n,Nt.GetAns());for(ll i1;ik;i)a[wz[q[i].p]].wa[wz[q[i].p]-1].w0;}return 0;
}
