J-SCP 加训记录
2026-08-24 21:22:40
发布于：浙江
前言
qy.1:
我是 区 。我只会 通过蠕动打字，所以，如果你，发，现了，我的，文章里，有错，无（比如这种错字），你可以，告诉我，我会，尝试，蠕动修改。
qy.2:
我的自测是 ，不会 LCS/LIS （比如说一些vector之类的神秘优化）和LCA（这个好像真不会），思维就是一坨。
qy.3:
由于我校的放学时间可能会有点晚，所以我不太会常更新这个帖子。
qy.4:
题目可能口胡可能给代码，因为 不能完全与pq1的帖子内容一样。
正题
T1。
好像就是模拟加一个二分，当然这题可以数学过，我好菜没写出来 。
#include <iostream>
using namespace syh;
int n, l, r, ans=0;
int check(int k)
{
while(k>=n) k-=n;
return k;
}
int main()
{
cin>>n>>l>>r;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)>=ans)
{
ans=check(mid);
l=mid+1;
}
else r=mid-1;
}
cout<<ans;
}
T1/2。
背包问题，枚举分数加人数即可满分，反正注意下百分数的运算就行。
#include <iostream>
using namespace syh;
int sc[605];
int main()
{
int n, w;
cin>>n>>w;
for(int i = 1;i<=n;i++)
{
int c, sum=0;
cin>>c;
sc[c]++;
int p=max(1,i*w/100);
for(int sco=600;sco>=0;sco--)
{
sum+=sc[sco];
if(sum>=p)
{
cout<<sco<<" ";
break;
}
}
}
}
T3。豆包老给我赛题干嘛/生气
不会做，打算骗分，哇，有十分是直接输出 就可以得到的，因为不花钱的选法肯定最佳（这就是“对于 的数据”那句话的打法）。
看一下 的情况，只要明天贵一点，今天就该能买多少买多少，明天卖掉就可以赚差价。
由这个 的情况可以得知，我们设计的 dp 只需要关注每天与下一天的差价即可，那么我们可以把题目当成完全背包做，只是每过一天要清空一次 dp 数组，那么每天的差价就是 p[i+1][j]-p[i][j]，当然这需要在明天更贵的情况下才会更新我们的 dp 数组，时间复杂度 。
#include <iostream>
#include <cstring>
using namespace syh;
int t, n, m, p[105][105], f[10005];
int main()
{
cin>>t>>n>>m;
for(int i = 1;i<=t;i++)
{
for(int j = 1;j<=n;j++)
{
cin>>p[i][j];
}
}
for(int i = 1;i<t;i++)//每次比较今天与明天
{
memset(f,0,sizeof f);//每次都是新一轮
//做完全背包
for(int j = 1;j<=n;j++)
{
if(p[i+1][j]>p[i][j])
{
//体积 p[i][j]，价值 a[i+1][j]-a[i][j]（差价）
for(int k = p[i][j];k<=m;k++)
{
f[k]=max(f[k],f[k-p[i][j]]+p[i+1][j]-p[i][j]);
}
}
}
m+=f[m];//f[m]为当天有m元最多赚的钱
}
cout<<m;
}
板死了不想讲，注意到答案为体积减去拿 个的最大体积，然后算一下，代码不给。
T4。
这题挺神的，代码的思路难想，读题可知，第 阶段的时候是直接相连的人给，第 () 个时，需要距离为 的所有工人参与追溯，最后找到原材料该谁给。
所以 ，题意就是 在无向图中，从 到 是否存在恰好长度为 的路径 ，因为可以重复的走，所以说是无向图，这里引入一个小定理，如果无向图中 能够在 步到达，那么它也可以在 等 偶数的步数到达，因为 可以走过去再走回来。
显然不可以暴力对吧，那我们跳过这一段。
显然要知道这张图的最短奇数路径和最短偶数路径，那么我们把 数组开成二维的用来存奇偶性不同的路径权值，在每次询问的时候对于 进行取模看是不是对应奇偶即可。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace syh;
int n, m, q;
vector<int> g[100005];
int dis[2][100005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>q;
for(int i = 1;i<=n;i++)
{
dis[0][i]=-1;
dis[1][i]=-1;
}
for(int i = 1;i<=m;i++)
{
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
queue<pair<int,int>> qu;
dis[0][1]=0;
qu.push({1,0});
while(!qu.empty())
{
int u=qu.front().first, p=qu.front().second;
qu.pop();
for(int v:g[u])
{
int np=p^1;//翻转一下奇偶
if(dis[np][v]==-1)
{
dis[np][v]=dis[p][u]+1;
qu.push({v,np});
}
}
}
while(q--)
{
int a;
long long l;
cin>>a>>l;
if(dis[l%2][a]==-1) cout<<"No\n";
else if(dis[l%2][a]<=l) cout<<"Yes\n";
else cout<<"No\n";
}
}
P3556 [POI 2013] MOR-Tales of seafaring
一道青，但是好像和上一题没啥区别，思路就和上题一样，但是这里的起点不再是 ，而是 ，所以我们要在每个故事里跑奇偶最短路，实现方法与上题几乎一样，这里不细讲。
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace syh;
typedef long long ll;
const int MAXN=5005;
vector<int> g[MAXN];
int n, m, k;
int dis[2][MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>k;
for(int i = 1;i<=m;i++)
{
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
while(k--)
{
int s, t, d;
cin>>s>>t>>d;
for(int i = 1;i<=n;i++)
{
dis[0][i]=-1;
dis[1][i]=-1;
}
queue<pair<int,int>> qp;
dis[0][s]=0;
qp.push({s,0});
while(!qp.empty())
{
int u=qp.front().first, p=qp.front().second;
qp.pop();
for(int v:g[u])
{
int np=p^1;
if(dis[np][v]==-1)
{
dis[np][v]=dis[p][u]+1;
qp.push({v,np});
}
}
}
int need=d%2;
if(dis[need][t]==-1) cout<<"NIE\n";
else if(dis[need][t]<=d) cout<<"TAK\n";
else cout<<"NIE\n";
}
}
时间复杂度 ，青++。
加你***这才 ，T掉了。
我太菜了这个当练习题写好了，需要达到的目的就是 。
有帮助，赞一个