cable cable cable
- 题意: M个灯,K个盒子,求最少要连多少条线,使任选K个盒子每个灯都能装下
- 思路: 每个灯要连(M-K+1)个 总共M*(M-K+1)
happy happy happy
- 题意: 左右取数,孩子每次都去左右两边最大的那个,父亲想让孩子赢(大于父亲)且最小化分差
- 思路: 限时搜索,先dp预处理出l,r区间最大分差和最小分差,然后\(2^n\)搜索,但每进入一层都要利用dp数组更新一次答案
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e2+10;
int n,a[N],mx[N][N],mn[N][N],ans;
int st,lim = 1000;
void init(){
memset(mx,-0x3f,sizeof mx);
memset(mn,0x3f,sizeof mn);
for(int i=1;i<=n+1;++i) mx[i][i-1] = mn[i][i-1] = 0;
for(int l=n;l>0;--l){
for(int r=l;r<=n;++r){
int ll = l,rr = r,son;
if(a[ll]>=a[rr]) son = a[ll++]; // 儿子取走左边的
else son = a[rr--]; // 取走右边的
mx[l][r] = max(mx[l][r],mx[ll][rr-1]+a[rr]-son); // 取左边
mx[l][r] = max(mx[l][r],mx[ll+1][rr]+a[ll]-son); // 取右边
mn[l][r] = min(mn[l][r],mn[ll][rr-1]+a[rr]-son);
mn[l][r] = min(mn[l][r],mn[ll+1][rr]+a[ll]-son);
}
}
}
void dfs(int l,int r,int dif){
if(l>r){ // 搜索到终点
if(dif<0) ans = max(ans,dif); // dif为当前爸爸比儿子少的
return ;
}
if(mn[l][r]+dif>=0 || mx[l][r]+dif<=ans) return ; // 可行性剪枝与最优化剪枝
if(mx[l][r]+dif<0){
ans = max(ans,mx[l][r]+dif);
return ;
}
if(clock()-st>lim) return ; // 超时停止搜索
int son;
if(a[l]>=a[r]) son = a[l++]; // 儿子优先拿大的
else son = a[r--];
dfs(l+1,r,dif+a[l]-son); // 取左边
dfs(l,r-1,dif+a[r]-son); // 取右边
}
int main(){
while(scanf("%d",&n)==1){
memset(a,0,sizeof a);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
init();
st = clock();
ans = -inf; // 爸爸比儿子少拿的 最后要取反
dfs(1,n,0);
if(ans == -inf) puts("The child will be unhappy...");
else printf("%d\n",-ans);
}
return 0;
}
array array array
- 题意: 一个序列,每次可以选最多k个数抹去,问能否变成一个非递增或非递减的序列
- 思路: dp求最长非递增l1,非递减序列的长度l2,max(l1,l2)+k>=n 就可以
number number number
- 题意: 求不能被k个斐波那契数组合出(可重复)的最小整数.
- 思路: 找规律可得为第k*2+3个斐波那契数,矩阵递推.
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 998244353;
struct mat{
ll a[2][2];
mat operator *(mat b){
mat res; res.a[0][0] = res.a[0][1] = res.a[1][0] = res.a[1][1] = 0;
for(int i=0;i<2;++i){
for(int k=0;k<2;++k){
for(int j=0;j<2;++j){
res.a[i][j] = (a[i][k] * b.a[k][j] %MOD + res.a[i][j])%MOD;
}
}
}
return res;
}
void init(){
a[0][0] = a[0][1] = a[1][0] = 1; a[1][1] = 0;
}
};
mat qpow(mat c,ll b){
mat res; res.a[0][0] = res.a[1][1] = 1; res.a[1][0] = res.a[0][1] = 0;
while(b){
if(b%2) res = res*c;
b>>=1;
c = c*c;
}
return res;
}
int main(){
ll k;
while(scanf("%lld",&k)!=EOF){
mat res; res.init();
res = qpow(res,k*2+3);
printf("%lld\n",(res.a[1][0]-1+MOD)%MOD);
}
return 0;
}
gems gems gems
- 题意: n堆石子从左往右拿,每次可以拿k或k+1堆(k为上一次拿的),A想最大化差异,B想最小化差异,问最后的差异是多少.
- 思路: 可以直接当做每个人都想最大化自己取到的石子,dp[i][j]表示还剩i堆石子,上一个人取了j堆时先手比后手多拿了多少石子
\(dp[i][j] = max(sum[i] - sum[i-j] - dp[i-j][j],sum[i] - sum[i-j-1] - dp[i-j-1][j+1](i>j))\)
因为n为2e4,每次拿k+1,k最大也只能取到sqrt(n).
#include<bits/stdc++.h>
using namespace std;
#define lson(p) (p<<1)
#define rson(p) (p<<1|1)
#define ll long long
const int N = 2e4+10;
int n,sum[N],v[N],f[N][202];
void gmax(int &a,int b){
if(b>a) a = b;
}
int main(){
int t; scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=n;i>=1;--i)// 反向dp,从后往前拿,所以输入要倒序
scanf("%d",&v[i]);
for(int i=1;i<=n;++i){
sum[i] = sum[i-1] + v[i];
}
int m = sqrt(n*2);
while((1+m)*m >n*2) --m;
for(int i=1;i<=n;++i){ // 还剩多少堆
int top = min(i,m);
for(int j=1;j<=top;++j){ // 当前这轮拿j堆
f[i][j] = sum[i] - sum[i-j] - f[i-j][j]; // 下次拿j堆
if(i>j) gmax(f[i][j],sum[i] - sum[i-j-1] - f[i-j-1][j+1]); // 下次拿j+1堆
}
}
printf("%d\n",f[n][1]); // 反向dp f[n][1] 为答案
}
return 0;
}
思路来源
transaction transaction transaction
- 题意: 一棵树,可以选择一个点出发,走到终点获得\(v[tp]-v[sp] - w\),终点价值-起点价值-路上花费,求最大收益
- 思路: 树形dp,0代表到这个点的最小花费,1代表卖出去的收益.(其实没必要那么麻烦,自己写挫了)
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e5+10;
struct node{
int u,v,w,nxt;
}e[N*2];
int head[N],tot;
int dp[N][2],a[N],n; // 0 买 1 卖
void add(int u,int v,int w){
e[tot] = (node){u,v,w,head[u]}; head[u] = tot++;
e[tot] = (node){v,u,w,head[v]}; head[v] = tot++;
}
void init(){
tot = 0; memset(head,-1,sizeof head);
memset(dp,0,sizeof dp);
}
void dfs(int u,int fa){
for(int i=head[u];~i;i=e[i].nxt){
if(e[i].v == fa) continue;
dp[e[i].v][0] = max(-a[e[i].v],dp[u][0]-e[i].w); // 儿子买
dp[e[i].v][1] = a[e[i].v] + dp[u][0] - e[i].w; // 儿子卖给父亲
dfs(e[i].v,u);
dp[u][1] = max(dp[e[i].v][0]+a[u] -e[i].w,dp[u][1]);
dp[u][0] = max(dp[e[i].v][0]-e[i].w,dp[u][0]);
}
}
int main(){
int t; scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
init();
int u,v,w;
for(int i=1;i<n;++i){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dp[1][0] = -a[1];
dfs(1,0);
int ans = 0;
for(int i=1;i<=n;++i){
ans = max(ans,dp[i][1]);
}
printf("%d\n",ans);
}
}
ping ping ping
- 题意: 一颗树,其中有些点是走不通的,给出Q个点对表示两点之间走不通,问最少有几个点是走不通的
- 思路: 贪心,每个点对,都让他们的lca走不通(lca可以控制最多的点),且先从lca较深的开始(较深的可以切断向较浅去的路径),用树剖求出dfs序及维护lca,L[u]~R[u]表示这个点掌控的范围(不在l~r区间内的点要到l~r必走u),用BIT维护区间修改,单点查询,每次割点就是L[u]+1,R[u]-1,而只要query(u)!=0则说明这个点已经有祖先被割掉了(因为是按lca深度由深到浅,不会出现先割祖先,再割后代,所以被割过就肯定走不通了);
#include<bits/stdc++.h>
using namespace std;
#define lson(p) (p<<1)
#define rson(p) (p<<1|1)
#define ll long long
const int N = 5e5+10;
struct Edge{
int u,v,w,nxt;
}e[N*2];
int head[N],tot;
int top[N],fa[N],deep[N],num[N],L[N],R[N],son[N]; // 重儿子
int pos;
void addedge(int u,int v,int w=0){e[tot] = (Edge){u,v,w,head[u]}; head[u] = tot++;}
struct node{
int u,v,la;
bool operator <(node b){
return deep[la] > deep[b.la];
}
};
vector<node> ve;
//第一遍dfs 处理fa,num,deep,son
void dfs1(int u,int pre,int d){
deep[u] = d;
fa[u] = pre;
num[u] = 1;
for(int i=head[u];~i;i=e[i].nxt){
int v = e[i].v;
if(v!=pre){
dfs1(v,u,d+1);
num[u] += num[v];
if(son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
}
// 第二遍dfs 处理 top,p,fp
void dfs2(int u,int sp){
top[u] = sp;
L[u] = ++pos;
if(son[u]== -1){
R[u] = pos ;
return ;
}
dfs2(son[u],sp); // 当前链继续走重儿子
for(int i=head[u];i!=-1;i=e[i].nxt){
int v = e[i].v;
if( v!= son[u] && v!=fa[u])
dfs2(v,v); // 以自己为链首的新链
}
R[u] = pos ;
}
int n,m;
struct BIT{
int a[N];
void init(){
memset(a,0,sizeof a);
}
int lowbit(int x){
return x&(-x);
}
void update(int x,int pos){
for(int i=pos;i<=n;i+=lowbit(i)) a[i] += x;
}
int query(int pos){
int res = 0;
for(int i=pos;i;i-=lowbit(i)) res += a[i];
return res;
}
}bt;
int lca(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]] > deep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
return deep[x] < deep[y] ? x:y;
}
void init(){
memset(head,-1,sizeof(head));memset(son,-1,sizeof(son));
bt.init();ve.clear();tot = 0;pos = 0;
}
int main(){
while(scanf("%d",&n)==1){
int u,v,ans=0;
init();
for(int i=1;i<=n;++i){
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs1(0,0,0); // 题目默认0为根节点
dfs2(0,0);
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
ve.push_back({u,v,lca(u,v)});
}
sort(ve.begin(),ve.end());
for(auto item:ve){
u = item.u, v = item.v;
if(bt.query(L[u]) || bt.query(L[v])) continue; // 已经被割掉的点覆盖
bt.update(1,L[item.la]) ; bt.update(-1,R[item.la]+1); // 割去他们的lca
ans++;
}
printf("%d\n",ans);
}
return 0;
}
card card card
- 题意: 两个序列a,b(\(\sum{a}=\sum{b}\)),每次向后走一步,sum+a[i]-b[i],能将最前面的一堆放到最后面,问要移多少堆才能拿到最后一堆
- 思路: 相对位置是不变的,直接求a[i]-b[i]的前缀和,最小即为答案
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e6+10;
int a[N],dp[N];
int n;
int main(){
while(scanf("%d",&n)==1){
int val;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&val); a[i]-=val;
}
int ans = 0,pos=0;
for(int i=1;i<=n;++i){
dp[i] = dp[i-1] + a[i];
if(dp[i]<ans){// 前缀和为负数是移不到最后的,要把最小的那个对应的堆数移到后面,则剩下的肯定全是正的
ans = dp[i];
pos = i;
}
}
printf("%d\n",pos);
}
}