做题日记
前言
本笔记是给自己看的，要简洁明了
6.14
P1892思路对了就很简单
6.19
P8647以后遇到题要从多方面想一想，比如：如果验证答案很容易，可以进行枚举，二分答案
一些基础的技术必须掌握！！，比如去重
set<int> se;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='.') cout<<'.';
else{
tmp=1;
se.insert(block[i][j+1]);
se.insert(block[i+1][j]);
se.insert(block[i][j-1]);
se.insert(block[i-1][j]);
for(auto i:se){
tmp+=ans[i];
}
se.clear();
cout<<tmp%10;
}
}
cout<<"\n";
}
6.25
CF189A:
dp要注意状态设计，问的是可以分成几段
别颓废了，赶紧做
dp[0]=1;
//dp[i][j]=max(dp[i-1][j-c[i]*k]*k,dp[i-1][j]);
//dp[j]=max(dp[j],dp[j-c[i]*k]*k);
for(int i=1;i<=n;i++){
for(int j=maxx;j>=1;j--){//对于每一个重量，考虑它可以从哪里转移过来
for(int l=0;l<=k[i]&&l*c[i]<=j;l++){//放在最内层
dp[j]=max(dp[j],dp[j-l*c[i]]*l);
}
cout<<dp[j]<<" ";
}
cout<<"\n";
}6.28
今天见到两类有趣的背包。一个是价值会随分配给他的空间变化，一个是总容量会变化的01背包（不选，容量增大，选择，容量减小）
P5322
这道题超级棒（自己独立做出来的），这个题目的难点在于“物品”的转化，以及选择时的限制。有
for(int i=1;i<=n;i++){
sort(a[i]+1,a[i]+1+s);
for(int j=1;j<=s;j++){
++cnt;
w[cnt]=a[i][j]*2+1;//当你给它的空间足够拥有它时
v[cnt]=i*j;//需要空间比他小的也可以得到
}
}但是在转移的时候，一列只能选一个（对一个城堡只有一种进攻方案），所以有了第三层循环
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
for(int k=(i-1)*s+1;k<=i*s;k++){
if(j>=w[k]) dp[j]=max(dp[j],dp[j-w[k]]+v[k]);
}
}
}P1156 这道题不太好做。要选择一些不变的量作为状态
CF294B 这题和上一个题有相似的地方
6.29
P2851
少用硬币：这道题有一些东西需要注意：1.店主要用完全背包算出凑出i的重量需要的最少硬币，但
// 先做完全背包
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=v[i];j<=sum;j++){
f[j]=min(f[j-v[i]]+1,f[j]);
}
}
cnt=n;
for(int i=1;i<=n;i++){
int tmp=1;
while(tmp<=c[i]){
v[++cnt]=v[i]*tmp;//重量
c[cnt]=tmp;//价值
c[i]-=tmp;
tmp=tmp<<1;
}
if(c[i]){
v[++cnt]=v[i]*c[i];
c[cnt]=c[i];
c[i]=0;
}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=n+1;i<=cnt;i++){
for(int j=sum;j>=v[i];j--){
dp[j]=min(dp[j],dp[j-v[i]]+c[i]);
}
}
// for(int i=1;i<=sum;i++) cout<<dp[i]<<" ";
// 接下来就是"P1102 A-B Problem"
int ans=INF;
for(int i=T;i<=sum;i++){
if(dp[i]<INF&&f[i-T]<INF){
ans=min(ans,dp[i]+f[i-T]);//注意：店主只能找零
}
}
if(ans==INF) cout<<-1<<"\n";
else cout<<ans<<"\n";7.5
今日任务： 1.询问物理 2.还书 3.学习割点与桥的知识 4.文化课
7.6
P1273 看题解做了一道题，没有完全理解怎办呢？
(有趣的事情：
P2607
这是一道
P4395 这道题的01染色是假的，以后要多想想
7.11
P3956
这道题非常有趣：在棋盘上跑
const int dx[]={0,1,0,-1,0,0,-1,1,2,-2,-1,1,0};
const int dy[]={0,0,1,0,-1,2,1,1,0,0,-1,-1,-2,};
for(int i=1;i<=12;i++){
int tx=tmp.x+dx[i];
int ty=tmp.y+dy[i];
if(tx<1||tx>m||ty<1||ty>m) continue;
if(vis[tx][ty]||a[tx][ty]==0) continue;
int val;
if(i<=4){//正常的向4个方向走
if(tmp.c==a[tx][ty]) val=0;
else val=1;
}
else{//使用魔法后
if(tmp.c==a[tx][ty]) val=2;
else val=3;
}
if(dis[tx][ty]>tmp.v+val){
dis[tx][ty]=tmp.v+val;
q.push({tx,ty,a[tx][ty],dis[tx][ty]});
}
}P1126
这道题的重点在于方向的控制，使用一个二维数组 if(a[tx][ty]||a[tx+1][ty]||a[tx][ty+1]||a[tx+1][ty+1]) break;//还要检查路径中有没有障碍物
7.21
P2719
概率
n/=2;
for(int i=2;i<=n;i++){
dp[i][0]=1; dp[0][i]=1;
}//其他票都卖光了
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i-1][j]*0.5+dp[i][j-1]*0.5;//重点理解转移方程：
}//每一个状态 dp [ i ] [ j ] 都是由 dp [ i - 1 ] [ j ] 和 dp [ i ] [ j - 1 ] 得到的
//理解：有0.5的概率从dp[i-1][j]转移过来（实际操作中是转移到dp[i-1][j]：卖出一张A），0.5的概率卖出B，
}P3197
md，思路相对了，代码写对了，取余处理好了，mod抄错了
//容斥：多少种会->多少种不会
Lon Sum=qpow(m,n);
Lon No=(m*qpow(m-1,n-1))%MOD;//不可以的情况
//cout<<Sum<<" "<<No<<"\n";
cout<<(Sum-No+MOD)%MOD<<"\n";//处理负数的情况7.26
树的进阶
CF1805D 这个题用到了树的性质
- 树上任意一个点出发到达最远的点必定是直径的一个
terminal ，换句话说，一个点出发到达最远的点是离他最远的那个直径端点
题目要求构建一个重构图（把树上距离大于k（k属于1-n）的点链接），求连通块的数量。我可以考虑最优的情况，把所有可能的点都连到端点上，通过端点连在一起。根据定理一，离一个点最远的点必定是一个端点。所以提前找到直径的这两个端点。定义i的距离为
如果k>直径，无法连接，有n个联通块，k==1，都可以链接，有1 个连通块，其他情况，能连接到直径端点的点是一个连通块，剩下的每个点都自己单独是连通块（因为我考虑的是最优的情况，他都不行，其它点更连不上）。用二分求解
P5536 树的直径
找到直径的中点（技术：输出路径）,然后贪心拓展
8.1
P8773
关键代码：
int lst[N],f[N];
for(int i=1;i<=n;i++){
f[i]=max(f[i-1],lst[a[i]^x]);
//1.当没有可以配对的时f[i]是0
//所以应对询问时-》见下面
lst[a[i]]=i;
//2.如果配对不行，比如 第4个数不可配对，但是第2，3可以。所以f[4]=2;
}
for(int i=1;i<=m;i++){
cin>>l>>r;
if(f[r]<l) cout<<"no\n";//f[r]记录允许的最大的左端点
else cout<<"yes\n";//至少要选择 f[r] -> r 这个区间
}