24.9.22（中秋佳节）
因为偷懒及种种原因，漏了一周周报，红豆泥私密马赛（鞠躬
周日：
本来不打算写今天的，但这题让我没蚌住，max_element() 越界了硬控我 1h
补cf round 972 div2 C 常规dp cf传送门
思路：dp【i】【j】表示考虑到第 i个（可滚动）以 j 结尾的最大分数
比较简单的转移，O(n*m)的复杂度，赛时wa了发后还以为得再套个 n的循环，把自己绕进去了
需要注意的是dp数组应初始化为一个极小值，可以很方便解决哪些字母状态合法的问题
代码如下：
const int N=2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
map<char,int>mp;
ll dp[1010][5];
inline bool ifc(char c){return c=='n'||c=='a'||c=='r'||c=='e'||c=='k';
}
void solve(){int m; cin >> n >> m;mp['n']=1,mp['a']=2,mp['r']=3,mp['e']=4,mp['k']=5;for(int i=0;i<=n;i++) for(int j=0;j<5;j++) dp[i][j]=-1e9;dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<5;j++) dp[i][j]=dp[i-1][j];string s; cin >> s;int sc[5]={0},to[5]={0,1,2,3,4}; //各个字母开头的分数及当前字母for(char c:s) if(ifc(c)){int num=mp[c];for(int j=0;j<5;j++){if(num==to[j]+1){to[j]++;if(to[j]==5) sc[j]+=5,to[j]=0;}else sc[j]--;}}for(int j=0;j<5;j++) dp[i][to[j]]=max(dp[i-1][j]+sc[j],dp[i][to[j]]);}for(int j=0;j<5;j++) dp[n][j]-=j;
// cout << max(*max_element(dp[n],dp[n]+5+1),0ll) << "\n"; 注意别越界cout << max(*max_element(dp[n],dp[n]+5),0ll) << "\n";
// for(int i=0;i<=n;i++)
// for(int j=0;j<5;j++) cout << dp[i][j] << " \n"[j==4];
}星期一：
vp了 CCPC 23年秦皇岛，4题罚时爆炸
G 简单签到
A题全程俩队友构造的
D 简单线段树题，将券按过期天数从小到大排，每次给最便宜的天用。然后将价格排序，遍历一遍就得到了 n个答案。线段树队友搓的，我写了个树上找范围内最小值下标的函数。
这题在卡 J的时候 osir出的，虽然过题人数比 J少点，但对我们来说比 J简单很多（破案了，原来是J的数据放了种贪心过了，osir还以为小登都会状压，给他吓一跳
J 状压dp cf传送门
百度之星决赛因为第四题状压dp，结果我掉进了暴力dfs+优化的坑里，痛失铜牌，今日幸而识出，ac破除心魔
思路：dp【mask】代表此状态最少天数，lef【mask】表示剩余体力
先将一天能拿下的单词集合的状态和所需体力处理出来，最多1<<13个
然后进行(1<<13) * (1<<13)的转移，第一关键字为天数，第二为体力，简单讨论下就可转移
代码如下：
const int N=1e5+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
int a[16];
int s[N],idx,ned[N];
ll dp[N],lef[N];
void solve(){ll w; cin >> n >> w;for(int i=1;i<=n;i++){int len; cin >> len;a[len-1]++; //注意和下标对上}const int mm=1<<13;for(int mask=0;mask<mm;mask++){int sum=0;for(int i=0;i<13;i++) if(mask&1<<i) sum+=a[i];if(sum<=w) s[++idx]=mask,ned[idx]=sum;}memset(dp,0x3f,sizeof dp);for(int mask=0;mask<mm;mask++) lef[mask]=w;dp[0]=1;for(int mask=0;mask<mm;mask++){for(int i=1;i<=idx;i++){ //1<<13 < 1e4int nmask=mask|s[i];
// dp[nmask]=min(dp[mask]+cnt[i],dp[nmask]);//开局瞎写的转移if(ned[i]<=lef[mask]){
// if(dp[nmask]>dp[mask]) dp[nmask]=dp[mask],lef[nmask]-=ned[i];if(dp[nmask]>dp[mask]) dp[nmask]=dp[mask],lef[nmask]=lef[mask]-ned[i];else if(dp[nmask]==dp[mask]) lef[nmask]=max(lef[mask]-ned[i],lef[nmask]);}else{if(dp[nmask]>dp[mask]+1) dp[nmask]=dp[mask]+1,lef[nmask]=w-ned[i];else if(dp[nmask]==dp[mask]+1) lef[nmask]=max(w-ned[i],lef[nmask]);}}}cout << dp[(1<<13)-1];
}cf edu round 107 D 简单构造 cf传送门
思路：要求尽量少的重复，例如abcd，容易想到ab+ac+ad+bc+bd+cd这样n^2的组合，再补上单字母重复，形成原初字符串，将其不断循环输出即可
代码如下：
ll n;
void solve(){int k; cin >> n >> k;vector<char>ve;for(int i=1;i<=k;i++) ve.push_back(char('a'+i-1));string s;for(int i=0,sz=ve.size();i<sz;i++){s+=ve[i];for(int j=i+1;j<sz;j++) s+=ve[i],s+=ve[j];}int sz=s.size();for(int i=0;i<n;i++) cout << s[i%sz];
}星期二：
不知不觉摸鱼了一天
星期三：
cf edu round136 D 二分+dfs cf传送门
之前做过类似题，不过这次半天没反应过来，看到题目的二分tag才想到怎么写
思路：框架是很典的二分+dfs，不过我wa了一发，因为切割并不能在往下d时就切，这样在某些情况，会比回溯时判断切割的花费大，换句话说，就是提前切更好，最好自己画个有分叉的树理解下
代码如下：
const int N=2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
vector<int>ve[N];
int sum;
inline int dfs(int x,int mid){int dep=1,ma=0;for(int v:ve[x]){int d=dfs(v,mid);if(dep+d>mid) sum++; //判断能不能接这颗子树,不能就花费+1else ma=max(d,ma);}return dep+ma;
}
void solve(){int k; cin >> n >> k;for(int i=1;i<=n;i++) ve[i].clear();for(int i=2;i<=n;i++){int p; cin >> p;ve[p].push_back(i);}ll l=1,r=n-1,res=0;while(l<=r){ll mid=l+r>>1;sum=0;for(int v:ve[1]) dfs(v,mid);if(sum<=k) res=mid,r=mid-1;else l=mid+1;}cout << res << "\n";
}cf edu round108 div2 D cf传送门
思路：有一丢区间dp的思想，rev【l】【r】表示翻转 l-r区间的乘积和
代码如下：
ll n;
ll a[5050],b[5050];
ll sum[5050];
ll rev[5050][5050];
void solve(){cin >> n;for(int i=1;i<=n;i++){cin >> a[i];}for(int i=1;i<=n;i++){cin >> b[i];sum[i]=b[i]*a[i]+sum[i-1];rev[i][i]=a[i]*b[i];}ll ans=sum[n];for(int i=1;i<n;i++){rev[i][i+1]=a[i]*b[i+1]+a[i+1]*b[i];ans=max(rev[i][i+1]+sum[i-1]+sum[n]-sum[i+1],ans);}for(int len=3;len<=n;len++){for(int l=1;l+len-1<=n;l++){int r=l+len-1;rev[l][r]=rev[l+1][r-1]+a[l]*b[r]+a[r]*b[l];ans=max(rev[l][r]+sum[l-1]+sum[n]-sum[r],ans);}}cout << ans << "\n";
}星期四：
cf edu round135 div2 D cf传送门
很有意思一道题
思路：dp【l】【r】表示从 l-r区间开始的结果，1表示A赢，-1表示B赢，0表示平局
奇数区间长度在题中并无意义，只枚举偶数长度的。先将长度为2的结果初始化
对于l-r区间，A有两种选择，拿s【l】或拿s【r】，对于A的两种选择，B也各有俩选择，举个例子 3-6区间，若A拿了s【3】，B可拿s【6】再进行 4-5的博弈（dp【4】【5】已知），B也可拿 s【4】进行 5-6的博弈（dp【5】【6】已知）。若B拿4，根据题意，后拿的字母放最前，所以若 5-6区间结果不为0，则dp【3】【6】=dp【5】【6】，若为平局则说明前面的字母都相同，此时比较s【3】和s【4】来判断结果，A拿3或6，B都会选结果最小的，则A再从选3和选6中取最大值
代码如下：
ll n;
int dp[2020][2020];
int cmp(char c1,char c2){if(c1==c2) return 0;if(c1<c2) return 1;if(c1>c2) return -1;
}
void solve(){string s; cin >> s;n=s.size(); s=" "+s;for(int i=1;i<n;i++) dp[i][i+1]=(s[i]==s[i+1])?0:1;for(int len=4;len<=n;len+=2){for(int l=1;l+len-1<=n;l++){int r=l+len-1;int d1=!dp[l+1][r-1]?cmp(s[l],s[r]):dp[l+1][r-1];int d2=!dp[l+2][r]?cmp(s[l],s[l+1]):dp[l+2][r];int d3=!dp[l+1][r-1]?cmp(s[r],s[l]):dp[l+1][r-1];int d4=!dp[l][r-2]?cmp(s[r],s[r-1]):dp[l][r-2];dp[l][r]=max(min(d1,d2),min(d3,d4));}}if(!dp[1][n]) cout << "Draw\n";else if(dp[1][n]==1) cout << "Alice\n";else cout << "Bob\n";
}星期五：
cf edu round 133 D cf传送门
因为开的 ll然后取模太多T了一发
思路：理解了题意后试着写了发最暴力的码，空间和时间都不达标，但能把样例跑出来，然后一步步优化空间和时间，就过了，需要注意，最开始的码仅是为了跑出样例所以答案没有取模，但后面优化完了也没想起把取模补上，所以白wa了发，算是一个比较典的失误，以后应注意
最开始的dp【i】【j】表示用 j步走到 i的方案数，用ans【i】记录答案后第二维可优化
这里简要说下最关键的优化时间的一步，以 n=8，k=1为例，k=2时，dp【8】从2，4，6转移， dp【7】从1，3，5转移，那么dp【6】呢，从2，4转移，可以发现6和8的区别即比8少了一个6， 5也是比7少了个5，实际上每k个数可看作一周期，我们只需要把第一个周期的答案算出来，后面的答案都可以根据上一个周期直接得到（ 和单调队列优化多重背包有一点像
代码如下：
const int N=2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
//ll dp[11][11];
//ll dp[N],ans[N];
int dp[N],ans[N];
void solve(){int k; cin >> n >> k;
// dp[0][0]=1;
// for(int r=1,st=k;st<=n;r++){
// for(int i=n;i>=st;i--)
// for(int j=i-k;j>=0;j-=k)
// dp[i][r]+=dp[j][r-1];
// st+=++k;
// }
// for(int i=1;i<=n;i++){
// int sum=0;
// for(int r=1;r<=n;r++) sum+=dp[i][r];
// cout << sum << " ";
// }dp[0]=1;for(int r=1,st=k,lst=0;st<=n;r++){
// for(int i=n;i>=st;i--){
// dp[i]=0;
// for(int j=i-k;j>=0;j-=k) dp[i]+=dp[j];
// ans[i]+=dp[i];
// }for(int i=n;i>n-k;i--){dp[i]=0;for(int j=i-k;j>=0;j-=k) (dp[i]+=dp[j])%=mod;(ans[i]+=dp[i])%=mod;}for(int i=n-k;i>=st;i--) dp[i]=(dp[i+k]-dp[i]+mod)%mod,(ans[i]+=dp[i])%=mod;for(int j=lst;j<st;j++) dp[j]=0;lst=st;st+=++k;}for(int i=1;i<=n;i++) cout << ans[i] << " ";
}cf edu round 110 D 线段树 cf传送门
奖励关
思路：这个比赛的结构看着就很像线段树，也确实可用线段树维护
节点信息有队伍范围（注意叶子节点 l==r-1，比赛结果oc，和可能胜出的队伍数win
如何知道哪个节点对应的是哪场比赛呢？有一个trick是将左孩子编号为*2+1，右孩子编号为*2， 这样节点的编号和代表的比赛的和即为 1<<k
代码如下：
const int N=3e5+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll n;
string s;
struct seg_Tree{
#define lc p<<1|1
#define rc p<<1struct nod{int l,r;char oc;int win;}t[N<<2];int ql,qr;char qv;void pushup(int p){if(t[p].oc=='0') t[p].win=t[lc].win;if(t[p].oc=='1') t[p].win=t[rc].win;if(t[p].oc=='?') t[p].win=t[lc].win+t[rc].win;}void bd(int p,int l,int r){t[p]={l,r,s[n-p],0};if(l==r-1){if(s[n-p]!='?') t[p].win=1;else t[p].win=2;return ;}int mid=l+r>>1;bd(lc,l,mid);bd(rc,mid+1,r);pushup(p);}void update(int p){if(ql<=t[p].l && qr>=t[p].r){t[p].oc=qv;if(qr>ql+1){ //讨论是否为叶子节点if(qv=='0') t[p].win=t[lc].win;else if(qv=='1') t[p].win=t[rc].win;else t[p].win=t[lc].win+t[rc].win;}else{if(qv=='?') t[p].win=2;else t[p].win=1;}return ;}int mid=t[p].l+t[p].r>>1;if(ql<=mid) update(lc);if(qr>mid) update(rc);pushup(p);}void updt(int l,int r,char v){ql=l,qr=r;qv=v;update(1);}
}tr;
void solve(){int k; cin >> k;n=1<<k;cin >> s;s=" "+s;tr.bd(1,1,n);int q; cin >> q;while(q--){int p;char c; cin >> p >> c;int l=tr.t[n-p].l,r=tr.t[n-p].r; //比赛p的队伍范围tr.updt(l,r,c);cout << tr.t[1].win << "\n";}
}周日：
补24百度之星决赛 A 组队 mtj传送门
思路：状压dp，赛时掉进了dfs+优化的坑里，状态需要预处理一下
注意两个点：1<<21的值大于2e6，数组空间要开大点
将组队的能力值预处理出来，每次用max{}会T！！，实测比挨个max都会慢很多
以后对于多个值取max的情况，慎用大括号
代码如下：
const int N=2.2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll a[22],b[22][22];
vector<int>s;
ll sc[22][22][22];
ll dp[N];
void solve(){cin >> n;for(int i=1;i<=n;i++) cin >> a[i];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin >> b[i][j];for(int mask=0;mask<1<<n;mask++)if(__builtin_popcount(mask)%3==0) s.push_back(mask);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)sc[i][j][k]=max({a[i],a[j],a[k],b[i][j],b[j][k],b[i][k],b[i][j]*b[j][k]*b[i][k]});for(int mask:s){vector<int>ve;for(int i=0;i<n;i++) if(!(mask&1<<i)) ve.push_back(i);for(int i=0,sz=ve.size();i<sz;i++){for(int j=i+1;j<sz;j++)for(int k=j+1;k<sz;k++){int x=ve[i],y=ve[j],z=ve[k];int nmask=mask|(1<<x)|(1<<y)|(1<<z);x++,y++,z++;
// ll sc=max({a[x],a[y],a[z],b[x][y],b[y][z],b[x][z],b[x][y]*b[y][z]*b[x][z]});//>2000ms,T掉
// ll sc=max(a[x],a[y]);
// sc=max(a[z],sc);
// sc=max(b[x][y],sc);
// sc=max(b[y][z],sc);
// sc=max(b[x][z],sc);
// sc=max(b[x][y]*b[y][z]*b[x][z],sc);//900ms,能过dp[nmask]=max(dp[mask]+sc[x][y][z],dp[nmask]); //600ms}}}cout << dp[(1<<n)-1];
}补 cf round947 div3 E dij cf传送门
思路：魔改dij，dis【i】【0/1】表示到 i点没骑/骑了马的最短距离，需要根据骑没骑马以及目标点有无马讨论，同时注意优先队列的优先级，是以距离最短为第一，都可以不管有无马
代码如下：
const int N=2e6+10,M=210;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
map<int,bool>ifh;
vector<PII>ve[N];
struct nod{ll x;ll ti;bool iff;bool operator <(const nod &b)const{
// if(iff!=b.iff) return iff<b.iff;
// else return ti>b.ti;if(ti!=b.ti) return ti>b.ti;return iff<b.iff; //不要也行}
};
ll dis1[N][2],disn[N][2];
map<PII,bool>vi;
void dij1(){
// memset(dis1,0x3f,sizeof dis1);for(int i=1;i<=n;i++) dis1[i][0]=dis1[i][1]=2e18;priority_queue<nod>pq;if(ifh.count(1)) pq.push({1,0,1}),dis1[1][1]=0;else pq.push({1,0,0});dis1[1][0]=0;while(!pq.empty()){nod t=pq.top(); pq.pop();if(vi.count({t.x,t.iff})) continue;vi[{t.x,t.iff}]=1;for(auto [w,v]:ve[t.x]){if(t.iff){if(dis1[v][1]>min(t.ti,dis1[t.x][1])+w/2){dis1[v][1]=t.ti+w/2;pq.push({v,dis1[v][1],1});}}else{if(ifh.count(v) && dis1[v][1]>min(t.ti,dis1[t.x][0])+w){dis1[v][1]=t.ti+w;pq.push({v,dis1[v][1],1});}else if(!ifh.count(v) && dis1[v][0]>min(t.ti,dis1[t.x][0])+w){dis1[v][0]=t.ti+w;pq.push({v,dis1[v][0],0});}}}}
}
void dijn(){
// memset(disn,0x3f,sizeof disn);for(int i=1;i<=n;i++) disn[i][0]=disn[i][1]=2e18;priority_queue<nod>pq;if(ifh.count(n)) pq.push({n,0,1}),disn[n][1]=0;else pq.push({n,0,0});disn[n][0]=0;while(!pq.empty()){nod t=pq.top(); pq.pop();if(vi.count({t.x,t.iff})) continue;vi[{t.x,t.iff}]=1;for(auto [w,v]:ve[t.x]){if(t.iff){if(disn[v][1]>min(t.ti,disn[t.x][1])+w/2){disn[v][1]=t.ti+w/2;pq.push({v,disn[v][1],1});}}else{if(ifh.count(v) && disn[v][1]>min(t.ti,disn[t.x][0])+w){disn[v][1]=t.ti+w;pq.push({v,disn[v][1],1});}else if(!ifh.count(v) && disn[v][0]>min(t.ti,disn[t.x][0])+w){disn[v][0]=t.ti+w;pq.push({v,disn[v][0],0});}}}}
}
void solve(){int m,h; cin >> n >> m >> h;ifh.clear();vi.clear();for(int i=1;i<=n;i++) ve[i].clear();for(int i=1;i<=h;i++){int a; cin >> a;ifh[a]=1;}for(int i=1;i<=m;i++){int u,v,w; cin >> u >> v >> w;ve[u].push_back({w,v});ve[v].push_back({w,u});}dij1();if(min(dis1[n][0],dis1[n][1])>1e18){cout << "-1\n"; return ;}vi.clear();dijn();ll ans=1e18;for(int i=1;i<=n;i++)ans=min(max(min(dis1[i][0],dis1[i][1]),min(disn[i][0],disn[i][1])),ans);cout << ans << "\n";
}