官方题目链接:http://118.190.20.162/
\(\Huge目录\)
- 201609
- 201612
- 201709
- 202104
- 202109
- 202112
- 202203
- 202206
- 202209
- 202303
- 202305
- 202309
\(\Huge\text{CSP201609}\)
火车购票
问题描述
请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。
假设一节车厢有20排、每一排5个座位。为方便起见,我们用1到100来给所有的座位编号,第一排是1到5号,第二排是6到10号,依次类推,第20排是96到100号。
购票时,一个人可能购一张或多张票,最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位,则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中(不考虑是否相邻)。
假设初始时车票全部未被购买,现在给了一些购票指令,请你处理这些指令。
输入格式
输入的第一行包含一个整数n,表示购票指令的数量。
第二行包含n个整数,每个整数p在1到5之间,表示要购入的票数,相邻的两个数之间使用一个空格分隔。
输出格式
输出n行,每行对应一条指令的处理结果。
对于购票指令p,输出p张车票的编号,按从小到大排序。
样例输入
4
2 5 4 2
样例输出
1 2
6 7 8 9 10
11 12 13 14
3 4
样例说明
- 购2张票,得到座位1、2。
- 购5张票,得到座位6至10。
- 购4张票,得到座位11至14。
- 购2张票,得到座位3、4。
评测用例规模与约定
对于所有评测用例,1 ≤ n ≤ 100,所有购票数量之和不超过100。
做法
按照题意模拟,只要当前五个座位空的位置足够放下就放入。
代码
#include<bits/stdc++.h>
using namespace std;
int least[25];
int main(){
for(int i=1;i<=20;i++) least[i]=5;
int n,a;
bool done;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
done=0;
for(int j=1;j<=20;j++){
if(least[j]>=a){
for(int k=1;k<=a;k++){
cout<<j*5-least[j]+k<<" ";
}
cout<<endl;
done=1;
least[j]-=a;
break;
}
}
if(!done){
int cnt=a;
for(int j=1;j<=20&&cnt;j++){
if(least[j]>=cnt){
for(int k=1;k<=cnt;k++) cout<<j*5-least[j]+k<<" ";
least[j]-=cnt;
cnt=0;
break;
}
for(int k=5-least[j]+1;k<=5;k++){
cout<<(j-1)*5+k<<" ";
cnt--;
}
least[j]=0;
}
cout<<endl;
}
}
return 0;
}
炉石传说
问题描述
《炉石传说:魔兽英雄传》(Hearthstone: Heroes of Warcraft,简称炉石传说)是暴雪娱乐开发的一款集换式卡牌游戏(如下图所示)。游戏在一个战斗棋盘上进行,由两名玩家轮流进行操作,本题所使用的炉石传说游戏的简化规则如下:
- 玩家会控制一些角色,每个角色有自己的生命值和攻击力。当生命值小于等于 0 时,该角色死亡。角色分为英雄和随从。
- 玩家各控制一个英雄,游戏开始时,英雄的生命值为 30,攻击力为 0。当英雄死亡时,游戏结束,英雄未死亡的一方获胜。
- 玩家可在游戏过程中召唤随从。棋盘上每方都有 7 个可用于放置随从的空位,从左到右一字排开,被称为战场。当随从死亡时,它将被从战场上移除。
- 游戏开始后,两位玩家轮流进行操作,每个玩家的连续一组操作称为一个回合。
- 每个回合中,当前玩家可进行零个或者多个以下操作:
- 召唤随从:玩家召唤一个随从进入战场,随从具有指定的生命值和攻击力。
- 随从攻击:玩家控制自己的某个随从攻击对手的英雄或者某个随从。
- 结束回合:玩家声明自己的当前回合结束,游戏将进入对手的回合。该操作一定是一个回合的最后一个操作。
- 当随从攻击时,攻击方和被攻击方会同时对彼此造成等同于自己攻击力的伤害。受到伤害的角色的生命值将会减少,数值等同于受到的伤害。例如,随从 X 的生命值为 HX、攻击力为 AX,随从 Y 的生命值为 HY、攻击力为 AY,如果随从 X 攻击随从 Y,则攻击发生后随从 X 的生命值变为 HX - AY,随从 Y 的生命值变为 HY - AX。攻击发生后,角色的生命值可以为负数。
将给出一个游戏的过程,要求编写程序模拟该游戏过程并输出最后的局面。
输入格式
输入第一行是一个整数 n,表示操作的个数。接下来 n 行,每行描述一个操作,格式如下:
<action> <arg1> <arg2> ...
其中
- summon
:当前玩家在位置 召唤一个生命值为 、攻击力为 的随从。其中 是一个 1 到 7 的整数,表示召唤的随从出现在战场上的位置,原来该位置及右边的随从都将顺次向右移动一位。 - attack
:当前玩家的角色 攻击对方的角色 。 是 1 到 7 的整数,表示发起攻击的本方随从编号, 是 0 到 7 的整数,表示被攻击的对方角色,0 表示攻击对方英雄,1 到 7 表示攻击对方随从的编号。 - end:当前玩家结束本回合。
注意:随从的编号会随着游戏的进程发生变化,当召唤一个随从时,玩家指定召唤该随从放入战场的位置,此时,原来该位置及右边的所有随从编号都会增加 1。而当一个随从死亡时,它右边的所有随从编号都会减少 1。任意时刻,战场上的随从总是从1开始连续编号。
输出格式
输出共 5 行。
第 1 行包含一个整数,表示这 n 次操作后(以下称为 T 时刻)游戏的胜负结果,1 表示先手玩家获胜,-1 表示后手玩家获胜,0 表示游戏尚未结束,还没有人获胜。
第 2 行包含一个整数,表示 T 时刻先手玩家的英雄的生命值。
第 3 行包含若干个整数,第一个整数 p 表示 T 时刻先手玩家在战场上存活的随从个数,之后 p 个整数,分别表示这些随从在 T 时刻的生命值(按照从左往右的顺序)。
第 4 行和第 5 行与第 2 行和第 3 行类似,只是将玩家从先手玩家换为后手玩家。
样例输入
8
summon 1 3 6
summon 2 4 2
end
summon 1 4 5
summon 1 2 1
attack 1 2
end
attack 1 1
样例输出
0
30
1 2
30
1 2
样例说明
按照样例输入从第 2 行开始逐行的解释如下:
- 先手玩家在位置 1 召唤一个生命值为 6、攻击力为 3 的随从 A,是本方战场上唯一的随从。
- 先手玩家在位置 2 召唤一个生命值为 2、攻击力为 4 的随从 B,出现在随从 A 的右边。
- 先手玩家回合结束。
- 后手玩家在位置 1 召唤一个生命值为 5、攻击力为 4 的随从 C,是本方战场上唯一的随从。
- 后手玩家在位置 1 召唤一个生命值为 1、攻击力为 2 的随从 D,出现在随从 C 的左边。
- 随从 D 攻击随从 B,双方均死亡。
- 后手玩家回合结束。
- 随从 A 攻击随从 C,双方的生命值都降低至 2。
评测用例规模与约定
- 操作的个数0 ≤ n ≤ 1000。
- 随从的初始生命值为 1 到 100 的整数,攻击力为 0 到 100 的整数。
- 保证所有操作均合法,包括但不限于:
- 召唤随从的位置一定是合法的,即如果当前本方战场上有 m 个随从,则召唤随从的位置一定在 1 到 m + 1 之间,其中 1 表示战场最左边的位置,m + 1 表示战场最右边的位置。
- 当本方战场有 7 个随从时,不会再召唤新的随从。
- 发起攻击和被攻击的角色一定存在,发起攻击的角色攻击力大于 0。
- 一方英雄如果死亡,就不再会有后续操作。
- 数据约定:
前 20% 的评测用例召唤随从的位置都是战场的最右边。
前 40% 的评测用例没有 attack 操作。
前 60% 的评测用例不会出现随从死亡的情况。
做法
按照题意模拟即可。
代码
#include<bits/stdc++.h>
using namespace std;
struct juese{
bool Hero;
int atk,hp;
};
vector<juese> a[2];
int main(){
int n;
cin>>n;
a[0].push_back({1,0,30});
a[1].push_back({1,0,30});
string op;
int x,y,z,now=0,ans=0;
for(int i=1;i<=n;i++){
cin>>op;
if(op=="summon"){
int zx=0;
cin>>x>>y>>z;
a[now].insert(a[now].begin()+x,{0,y,z});
}
if(op=="attack"){
cin>>x>>y;
a[now][x].hp-=a[now^1][y].atk;
a[now^1][y].hp-=a[now][x].atk;
if(a[now][x].hp<=0&&x){
a[now].erase(a[now].begin()+x);
}
if(a[now^1][y].hp<=0&&y){
a[now^1].erase(a[now^1].begin()+y);
}
}
if(op=="end") now^=1;
}
if(a[0][0].hp>0&&a[1][0].hp>0) cout<<0<<endl;
else if(a[0][0].hp>0) cout<<1<<endl;
else cout<<-1<<endl;
for(int i=0;i<=1;i++){
cout<<a[i][0].hp<<endl;
cout<<a[i].size()-1<<" ";
for(int j=1;j<a[i].size();j++) cout<<a[i][j].hp<<" ";
cout<<endl;
}
return 0;
}
交通规划
问题描述
G国国王来中国参观后,被中国的高速铁路深深的震撼,决定为自己的国家也建设一个高速铁路系统。
建设高速铁路投入非常大,为了节约建设成本,G国国王决定不新建铁路,而是将已有的铁路改造成高速铁路。现在,请你为G国国王提供一个方案,将现有的一部分铁路改造成高速铁路,使得任何两个城市间都可以通过高速铁路到达,而且从所有城市乘坐高速铁路到首都的最短路程和原来一样长。请你告诉G国国王在这些条件下最少要改造多长的铁路。
输入格式
输入的第一行包含两个整数n, m,分别表示G国城市的数量和城市间铁路的数量。所有的城市由1到n编号,首都为1号。
接下来m行,每行三个整数a, b, c,表示城市a和城市b之间有一条长度为c的双向铁路。这条铁路不会经过a和b以外的城市。
输出格式
输出一行,表示在满足条件的情况下最少要改造的铁路长度。
样例输入
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
样例输出
11
评测用例规模与约定
对于20%的评测用例,1 ≤ n ≤ 10,1 ≤ m ≤ 50;
对于50%的评测用例,1 ≤ n ≤ 100,1 ≤ m ≤ 5000;
对于80%的评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 50000;
对于100%的评测用例,1 ≤ n ≤ 10000,1 ≤ m ≤ 100000,1 ≤ a, b ≤ n,1 ≤ c ≤ 1000。输入保证每个城市都可以通过铁路达到首都。
做法
按照题目建出最短路树。
代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int to,va;
};
vector<node> v[10005];
int dis[10005];
int n,m,x,y,z;
bool vis[10005];
struct my_cmp{
bool operator()(node a,node b){
return a.va>b.va;
}
};
priority_queue<node,vector<node>,my_cmp> q;
void dij(){
int p;
q.push(node{1,0});
while(!q.empty()){
p=q.top().to;
if(vis[p]){
q.pop();
continue;
}
vis[p]=1;
q.pop();
for(int i=0;i<v[p].size();i++){
int x=v[p][i].to;
if(dis[x]>dis[p]+v[p][i].va){
dis[x]=dis[p]+v[p][i].va;
q.push(node{x,dis[x]});
}
}
}
}
int ans;
int dfs(int now){
int mn=0x3f3f3f3f;
for(int i=0;i<v[now].size();i++){
if(dis[v[now][i].to]+v[now][i].va==dis[now])
mn=min(mn,v[now][i].va);
}
return mn;
}
int main(){
cin>>n>>m;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
v[x].push_back(node{y,z});
v[y].push_back(node{x,z});
}
dis[1]=0;
dij();
for(int i=2;i<=n;i++) ans+=dfs(i);
cout<<ans<<endl;
return 0;
}
祭坛
问题描述
在遥远的Dgeak大陆,生活着一种叫做Dar-dzo-nye的怪物。每当这种怪物降临,人们必须整夜对抗怪物而不能安睡。为了乞求这种怪物不再降临,人们决定建造祭坛。
Dgeak大陆可以看成一个用平面直角坐标系表示的巨大平面。在这个平面上,有 n 个Swaryea水晶柱,每个水晶柱可以用一个点表示。
如果 4 个水晶柱依次相连可以构成一个四边形,满足其两条对角线分别平行于 x 轴和 y 轴,并且对角线的交点位于四边形内部(不包括边界),那么这 4 个水晶柱就可以建立一个结界。其中,对角线的交点称作这个结界的中心。
例如下左图中,水晶柱 ABCD 可以建立一个结界,其中心为 O。
为了起到抵御Dar-dzo-nye的最佳效果,人们会把祭坛修建在最多层结界的保护中。其中不同层的结界必须有共同的中心,这些结界的边界不能有任何公共点,并且中心处也不能有水晶柱。这里共同中心的结界数量叫做结界的层数。
为了达成这个目的,人们要先利用现有的水晶柱建立若干个结界,然后在某些结界的中心建立祭坛。
例如上右图中,黑色的点表示水晶柱(注意 P 和 O 点不是水晶柱)。祭坛的一个最佳位置为 O 点,可以建立在 3 层结界中,其结界的具体方案见下左图。当然,建立祭坛的最佳位置不一定是唯一,在上右图中,O 点左侧 1 单位的点 P 也可以建立一个在 3 层结界中的祭坛,见下右图。
现在人们想知道:
- 祭坛最佳选址地点所在的结界层数;
- 祭坛最佳的选址地点共有多少个。
输入格式
输入的第一行包含两个正整数 n,q,表示水晶柱的个数和问题的种类。保证 q=1 或 2,其意义见输出格式。
接下来 n 行,每行包含两个非负整数 x,y,表示每个水晶柱的坐标。保证相同的坐标不会重复出现。
输出格式
若 q=1,输出一行一个整数,表示祭坛最多可以位于多少个结界的中心;若 q=2,输出一行一个整数,表示结界数最多的方案有多少种。
样例输入
26 1
0 5
1 1
1 5
1 9
3 5
3 10
4 0
4 1
4 2
4 4
4 6
4 9
4 11
5 0
5 2
5 4
5 8
5 9
5 10
5 11
6 5
7 5
8 5
9 10
10 2
10 5
样例输出
3
样例输入
26 2
0 5
1 1
1 5
1 9
3 5
3 10
4 0
4 1
4 2
4 4
4 6
4 9
4 11
5 0
5 2
5 4
5 8
5 9
5 10
5 11
6 5
7 5
8 5
9 10
10 2
10 5
样例输出
2
样例说明
样例即为题目描述中的例子,两个样例数据相同,分别询问最多的结界数量和达到最多结界数量的方案数。
其中图片的左下角为原点,右和上分别是 x 轴和 y 轴的正方向,一个格子的长度为单位长度。
以图中的 O 点建立祭坛,祭坛最多可以位于 3 个结界的中心。不存在更多结界的方案,因此样例1的答案为 3。
在 O 点左侧 1 单位的点 (4,5) 也可以建立一个在 3 个结界中的祭坛,因此样例2的答案为 2。
评测用例规模与约定
对于所有的数据,保证存在至少一种方案,使得祭坛建造在至少一层结界中,即不存在无论如何祭坛都无法建造在结界中的情况。
数据分为 8 类,各类之间互相没有交集,分别有以下特点:
占数据的 10%,\(n=200\),\(x,y\le n\);
占数据的 10%,\(n=200\),\(x,y\le 10^9\);
占数据的 10%,\(n=1000\),\(x,y\le n\);
占数据的 10%,\(n=1000\),\(x,y\le 10^9\);
占数据的 10%,\(n=5000\),\(x,y\le n\);
占数据的 10%,\(n=5000\),\(x,y\le 10^9\);
占数据的 20%,\(n=3\times10^5\),\(x,y\le n\);
占数据的 20%,\(n=3\times10^5\),\(x,y\le 10^9\)。
此外,每类数据中,q=1 与 q=2 各占恰好一半。
做法
待补。
大概是线段树乱斗。
代码
#include<bits/stdc++.h>
using namespace std;
#define MX 300005
int n,q;
int ans=0;
long long cnt=0;
int x[MX],y[MX];
struct point{
int x,y;
}ps[MX];
bool operator <(point a,point b){
if(a.y!=b.y) return a.y<b.y;
return a.x<b.x;
}
int u[MX],d[MX],s[MX];
int mx,my;
int sz[MX];
int szclear(){
for(int i=1;i<=mx;i++) sz[i]=0;
}
int szinc(int p,int v){
while(p<=mx){
sz[p]+=v;
p=(p|(p-1))+1;
}
}
int szsum(int p){
int res=0;
while(p){
res+=sz[p];
p&=p-1;
}
return res;
}
struct node{
int mx;
}a[MX*4];
void build(int id,int l,int r){
if(l==r){
a[id].mx=0;
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void change(int id,int l,int r,int p,int v){
if(l==r){
a[id].mx=v;
return;
}
int mid=(l+r)/2;
if(p<=mid) change(id*2,l,mid,p,v);
else change(id*2+1,mid+1,r,p,v);
a[id].mx=max(a[id*2].mx,a[id*2+1].mx);
}
int query(int id,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r){
return a[id].mx;
}
int mid=(l+r)/2;
int vl=0,vr=0;
if(ql<=mid) vl=query(id*2,l,mid,ql,qr);
if(qr>mid) vr=query(id*2+1,mid+1,r,ql,qr);
return max(vl,vr);
}
int lisanhua(int *v){
map<int,int> mp;
for(int i=1;i<=n;i++) mp[v[i]]=1;
int cur=0;
for(auto &pr:mp) pr.second=++cur;
for(int i=1;i<=n;i++) v[i]=mp[v[i]];
return cur;
}
void shuru(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
mx=lisanhua(x);
my=lisanhua(y);
for(int i=1;i<=n;i++) ps[i].x=x[i],ps[i].y=y[i];
sort(ps+1,ps+n+1);
}
void update(int px){
int oldS=s[px];
int newS=s[px]=min(u[px],d[px]);
change(1,1,mx,px,newS);
if(oldS<ans&&newS>=ans) szinc(px,1);
else if(oldS>=ans&&newS<ans) szinc(px,-1);
}
int Max(int xa,int xb){
if(xa>xb) return 0;
return query(1,1,mx,xa,xb);
/*
int maxs=0;
for(int i=xa;i<=xb;i++){
if(s[i]>maxs) maxs=s[i];
}
return maxs;
*/
}
int calc(int xa,int xb){
return szsum(xb)-szsum(xa-1);
/*
int res=0;
for(int i=xa;i<=xb;i++){
if(s[i]>=ans) ++res;
}
return res;*/
}
void chuli(bool second){
for(int i=1;i<=mx;i++) u[i]=d[i]=s[i]=0;
for(int i=1;i<=n;i++) u[ps[i].x]++;
szclear();
build(1,1,mx);
int st,ed=1;
ps[n+1].y=my+1;
for(int cury=1;cury<=my;cury++){
st=ed;
while(ps[ed].y==cury) ed++;
for(int i=st;i<ed;i++){
u[ps[i].x]--;update(ps[i].x);
}
int tl=0,tr=ed-st;
for(int i=st+1;i<ed;i++){
tl++;tr--;
if(!second){
int A=Max(ps[i-1].x+1,ps[i].x-1);
int B=min(A,min(tl,tr));
if(B>ans) ans=B;
}else{
if(tl<ans||tr<ans) continue;
cnt+=calc(ps[i-1].x+1,ps[i].x-1);
}
}
for(int i=st;i<ed;i++){
d[ps[i].x]++;update(ps[i].x);
}
}
}
int main(){
ios::sync_with_stdio(0);
shuru();
chuli(0);
if(q==1){
cout<<ans<<endl;
return 0;
}
chuli(1);
cout<<cnt<<endl;
return 0;
}
\(\Huge\text{CSP201612}\)
中间数
做法
先排序,对于每个数直接二分出它的最后位置,如果这个数形成的区间两侧数的数量相等则符合条件。
代码
#include<bits/stdc++.h>
using namespace std;
int n,a[1005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
bool db=0;
for(int i=1;i<=n;i++){
if(a[i]==a[i-1])continue;
int l=i,r=upper_bound(a+1,a+n+1,a[i])-a-1;
if(l-1==n-r)cout<<a[i]<<endl,db=1;
}
if(!db)cout<<-1<<endl;
return 0;
}
工资计算
做法
二分,具体部分直接分类讨论。
代码
#include<bits/stdc++.h>
using namespace std;
int calc(int s){
if(s<3500)return s;
int a=s-3500;
return-(min(1500,a)*0.03+
min(4500-1500,max(a-1500,0))*0.1+
min(9000-4500,max(a-4500,0))*0.2+
min(35000-9000,max(a-9000,0))*0.25+
min(55000-35000,max(a-35000,0))*0.3+
min(80000-55000,max(a-55000,0))*0.35+
max(a-80000,0)*0.45)+s;
}
int main(){
int t;cin>>t;
int l=0,r=1e4,ans=-1,mid;
while(l<=r){
mid=l+r>>1;
int s=calc(mid*100);
if(s==t){
ans=mid;
break;
}
if(s<t)l=mid+1;
else r=mid-1;
}
cout<<ans*100<<endl;
return 0;
}
权限查询
做法
按题意直接模拟。
代码
#include<bits/stdc++.h>
using namespace std;
int p,r,u,q;
unordered_map<string,int>mxlv;
unordered_map<string,unordered_map<string,int>>role;
unordered_map<string,unordered_map<string,int>>user;
int main(){
cin>>p;
for(int i=1;i<=p;i++){
string s;
cin>>s;
if(~s.find(":")){
string name;int lv=0,pos=0;
while(s[pos]!=':')name+=s[pos++];
pos++;
while(pos<s.size())lv=lv*10+s[pos++]-48;
mxlv[name]=lv;
}else mxlv[s]=1;
}
cin>>r;
for(int i=1;i<=r;i++){
string name;cin>>name;
int cnt;cin>>cnt;
while(cnt--){
string s;cin>>s;
if(~s.find(":")){
string nm;int lv=0,pos=0;
while(s[pos]!=':')nm+=s[pos++];
pos++;
while(pos<s.size())lv=lv*10+s[pos++]-48;
role[name][nm]=max(role[name][nm],lv);
}else role[name][s]=51145141;
}
}
cin>>u;
for(int i=1;i<=u;i++){
string name;cin>>name;
int cnt;cin>>cnt;
while(cnt--){
string s;cin>>s;
for(auto i:role[s])user[name][i.first]=max(user[name][i.first],i.second);
}
}
cin>>q;
for(int i=1;i<=q;i++){
string a,b;
cin>>a>>b;
if(~b.find(":")){
string nm;int lv=0,pos=0;
while(b[pos]!=':')nm+=b[pos++];
pos++;
while(pos<b.size())lv=lv*10+b[pos++]-48;
if(user[a].count(nm)&&user[a][nm]>=lv&&user[a][nm]!=51145141)cout<<"true\n";
else cout<<"false\n";
}else{
if(!user[a].count(b))cout<<"false\n";
else if(user[a][b]==51145141)cout<<"true\n";
else cout<<user[a][b]<<'\n';
}
}
return 0;
}
压缩编码
做法
题目中要求编码字典序递增,这就让我们想到他们的第一位一定是一段 0 和一段 1。
去掉第一位之后两个子段都分别递增,于是考虑区间 dp。
合并两个区间的时候直接增加他们的和。
直接把合并石子的代码粘上来就过了
代码
#include<bits/stdc++.h>
using namespace std;
int n,a[1005];
long long s[1005];
long long dp[1005][1005];
int main(){
cin>>n;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
dp[i][i]=0;
}
for(int l=2;l<=n;l++){
for(int i=1;i+l-1<=n;i++){
int j=i+l-1;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],s[j]-s[i-1]+dp[i][k]+dp[k+1][j]);
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
卡牌游戏
做法
读完题和样例解释之后就能发现这个状压 dp 是一个类似于不断迭代直到收敛的过程。
但是答案只保留五位小数,因此可以对每个状态直接迭代 1000 次。
代码
待补。
\(\Huge\text{CSP201709}\)
公共钥匙盒
做法
按照题意模拟即可。
代码
#include<bits/stdc++.h>
using namespace std;
struct DS{
int t;
int key;
bool qu;
bool operator >(const DS b)const{
if(t!=b.t) return t>b.t;
if(qu!=b.qu) return qu>b.qu;
return key>b.key;
}
};
int a[1005];
priority_queue<DS,vector<DS>,greater<DS> > q;//1=取,0=还
DS now;
int n;
int findfirst(int x){
for(int i=1;i<=n;i++) if(a[i]==x) return i;
return -1;
}
int main(){
int k;
int w,s,c;
cin>>n>>k;
for(int i=1;i<=n;i++) a[i]=i;
for(int i=1;i<=k;i++){
cin>>w>>s>>c;
q.push({s,w,1});
q.push({c+s,w,0});
}
while(!q.empty()){
now=q.top();
q.pop();
//cout<<now.t<<" "<<now.key<<" "<<now.qu<<endl;
if(now.qu){
a[findfirst(now.key)]=0;
}else{
a[findfirst(0)]=now.key;
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
JSON 查询
做法
按照题意模拟即可。
代码
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
struct node{
unordered_map<string,string> zifuchuan;
unordered_map<string,int> obj;
}a[105];
int v=1;
int n,m,l;
string s,t,r;
string geted;
int getstr(int sta){
geted="";int i;
for(i=sta+1;s[i]!='\"';i++){
if(s[i]=='\\'){
geted+=s[i+1];
i++;
}else geted+=s[i];
}
//cout<<"string start at "<<sta<<" is "<<geted<<endl;
return i+1;
}
int calcobj(int root,int sta){
//cout<<root<<" "<<sta<<endl;
bool jianzhi=0;
string jian,zhi;jian=zhi="";
int i;
for(i=sta+1;;){
if(s[i]==','||s[i]=='}'){
if(zhi!=""){
a[root].zifuchuan[jian]=zhi;
//cout<<root<<"."<<jian<<"="<<zhi<<endl;
}
jian=zhi="";
jianzhi=0;
}
if(s[i]=='}') break;
if(s[i]==':'){
jianzhi=1;
}
if(s[i]=='\"'){
i=getstr(i)-1;
if(!jianzhi) jian=geted;
else zhi=geted;
}
if(s[i]=='{'){
a[root].obj[jian]=++v;
i=calcobj(v,i);
}
i++;
}
return i;
}
int main(){
cin>>n>>m;
s="";
for(int i=1;i<=n+1;i++){
getline(cin,t);
s+=t;
}
//cout<<s<<endl;
calcobj(1,0);
int nowrt;
bool f,zfc;
for(int i=1;i<=m;i++){
cin>>t;
t+='.';
l=t.length();
r="";
nowrt=1;
f=0;zfc=0;
for(int j=0;j<l;j++){
if(t[j]=='.'){
//cout<<r<<"("<<nowrt<<endl;
if(a[nowrt].obj[r]) nowrt=a[nowrt].obj[r],r="";
else if(a[nowrt].zifuchuan[r]==""){
f=1;
break;
}else zfc=1;
}else r+=t[j];
}
if(f) cout<<"NOTEXIST"<<endl;
else{
if(zfc) cout<<"STRING "<<a[nowrt].zifuchuan[r]<<endl;
else cout<<"OBJECT"<<endl;
}
}
return 0;
}
通信网络
做法
找出强连通分量,这里面的人都是互相知道的。
缩点之后直接 bfs 即可。
代码
#include<bits/stdc++.h>
using namespace std;
vector<int> v[2][10005];
bool in[10005];
int dfn[10005],low[10005],sum=0;
int sz[10005],belong[10005],tot=0;
bool b[2][10005];
stack<int> s;
void dfs(int u){
in[u]=1;
s.push(u);
dfn[u]=low[u]=++sum;
for(int i=0;i<v[0][u].size();i++){
int to=v[0][u][i];
if(dfn[to]==0){
dfs(to);
low[u]=min(low[u],low[to]);
}else if(in[to]){
low[u]=min(low[u],dfn[to]);
}
}
if(dfn[u]==low[u]){
int cnt=1;
in[u]=0;
++tot;
belong[u]=tot;sz[u]=1;
while(s.top()!=u){
in[s.top()]=0;
belong[s.top()]=tot;
sz[u]++;
s.pop();
cnt++;
}
s.pop();
}
}
queue<int> q;
void ltk(int num,int u){
while(!q.empty()) q.pop();
memset(b[num],0,sizeof(b[num]));
b[num][u]=1;
q.push(u);
int now,to;
while(!q.empty()){
now=q.front();
q.pop();
for(int i=0;i<v[num][now].size();i++){
to=v[num][now][i];
if(!b[num][to]){
b[num][to]=1;
q.push(to);
}
}
}
}
int n,m;
bool find(){
for(int i=1;i<=n;i++){
if(!b[0][i]&&!b[1][i]) return 0;
}
return 1;
}
int main(){
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
v[0][x].push_back(y);
v[1][y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) dfs(i);
}
int ans=0;
for(int i=1;i<=n;i++){
if(sz[i]){
ltk(0,i);ltk(1,i);
if(find()) ans+=sz[i];
}
}
cout<<ans<<endl;
return 0;
}
除法
做法
待补
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100005,M=1000005;
struct query{
int op;
int l,r,v;
}qaq[N];
int n,m;
int a[N];
ll c[N];
#define lowbit(x) (x&-x)
void add(int now,int u){
while(now<=n){
c[now]+=u;
now+=lowbit(now);
}
}
ll sum(int now){
ll ans=0;
while(now){
ans+=c[now];
now-=lowbit(now);
}
return ans;
}
set<int> tpos[M],v;
void yinshu_jia(int x){
for(int i=1;i*i<=a[x];i++){
if(a[x]%i) continue;
if(v.find(i)!=v.end()) tpos[i].insert(x);
if(v.find(a[x]/i)!=v.end()&&i*i!=a[x]) tpos[a[x]/i].insert(x);
}
}
void yinshu_jian(int x){
for(int i=1;i*i<=a[x];i++){
if(a[x]%i) continue;
if(tpos[i].find(x)!=tpos[i].end()) tpos[i].erase(x);
if(tpos[a[x]/i].find(x)!=tpos[a[x]/i].end()&&i*i!=a[x]) tpos[a[x]/i].erase(x);
}
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);
}
for(int i=1;i<=m;i++){
cin>>qaq[i].op>>qaq[i].l>>qaq[i].r;
if(qaq[i].op==1){
cin>>qaq[i].v;
if(qaq[i].v^1){
v.insert(qaq[i].v);
}
}
}
for(int i=1;i<=n;i++) yinshu_jia(i);
for(int k=1;k<=m;k++){
int op=qaq[k].op,l=qaq[k].l,r=qaq[k].r,t=qaq[k].v;
if(op==1){
for(auto j=tpos[t].lower_bound(l);j!=tpos[t].end()&&*j<=r;){
int i=*j;j++;
add(i,-a[i]+a[i]/t);
tpos[t].erase(i);
yinshu_jian(i);
a[i]/=t;
if(a[i]!=1) yinshu_jia(i);
}
}else cout<<sum(r)-sum(l-1)<<endl;
}
return 0;
}
\(\Huge\text{CSP202104}\)
灰度直方图
做法
直接做。
代码
#include<iostream>
using namespace std;
int a[1005],x;
int main(){
int n,m,l;
cin>>n>>m>>l;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>x;
a[x]++;
}
}
for(int i=0;i<l;i++) cout<<a[i]<<" ";
cout<<endl;
return 0;
}
邻域均值
做法
预处理前缀和然后直接做。
代码
#include<iostream>
using namespace std;
int a[605][605];
int s[605][605];
int main(){
int n,l,r,t,cnt,sum,ans=0,x1,y1,x2,y2;
cin>>n>>l>>r>>t;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
x1=i-r;
x2=i+r;
y1=j-r;
y2=j+r;
if(x1<1) x1=1;
if(x2>n) x2=n;
if(y1<1) y1=1;
if(y2>n) y2=n;
sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
cnt=(x2-x1+1)*(y2-y1+1);
if(sum*1.0/cnt<=t) ans++;
}
}
cout<<ans<<endl;
return 0;
}
DHCP服务器
题面
详见我的博客中本题题解。
校门外的树
做法
待补,好像是 dp
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1e5+5,P=1e9+7;
int n,a[1005],ff[1005][1005];
long long f[1005][1005];
bool v[MAXN];
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int nn=a[n];
for(int i=n-1;i>=1;i--){
memset(v,0,sizeof(v));
for(int j=i+1;j<=n;j++){
for(int k=i+1;k<j;k++) f[i][j]+=f[i][k]*ff[k][j]%P;
int num=a[j]-a[i],c=0,k;
for(k=1;k*k<=num;k++){
if(num%k>0) continue;
if(!v[k]) c++,v[k]=1;
if(!v[num/k]) c++,v[num/k]=1;
}
f[i][j]=(f[i][j]+(ff[i][j]=c-1))%P;
}
}
cout<<f[1][n]<<endl;
return 0;
}
\(\Huge\text{CSP202109}\)
数组推导
做法
直接做。
代码
#include<iostream>
using namespace std;
int b[105];
int main(){
int n,ans1=0,ans2=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>b[i];
if(b[i]!=b[i-1]) ans1+=b[i];
ans2+=b[i];
}
cout<<ans2<<endl<<ans1<<endl;
return 0;
}
非零段划分
题面
见我博客中本题题解。
脉冲神经网络
题面
见我博客中本题题解。
收集卡牌
题面
见我博客中本题题解。
\(\Huge\text{CSP202112}\)
火大,题没补,先咕了。
\(\Huge\text{CSP202203}\)
火大,也没补完
\(\Huge\text{CSP202206}\)
寻宝!大冒险!
代码
#include<bits/stdc++.h>
using namespace std;
int n,L,S;
bool b[2505][2505];
map<pair<int,int>,bool> vis;
vector<pair<int,int> > v1,v2,v3;
int main(){
cin>>n>>L>>S;
for(int i=1,x,y;i<=n;i++){
cin>>x>>y;
v1.push_back(make_pair(x,y));
vis[make_pair(x,y)]=1;
}
for(int i=0;i<=S;i++){
for(int j=0;j<=S;j++){
cin>>b[S-i][j];
if(b[S-i][j]&&S-i+j>0) v2.push_back(make_pair(S-i,j));
if(!b[S-i][j]) v3.push_back(make_pair(S-i,j));
}
}
int ans=0;
for(int i=0;i<n;i++){
if(v1[i].first+S>L||v1[i].second+S>L) continue;
bool flg=1;
for(auto j:v2){
if(!vis[make_pair(j.first+v1[i].first,j.second+v1[i].second)]){
flg=0;
break;
}
}
if(!flg) continue;
for(auto j:v3){
if(vis[make_pair(j.first+v1[i].first,j.second+v1[i].second)]){
flg=0;
break;
}
}
ans+=flg;
}
cout<<ans<<endl;
return 0;
}
角色授权
代码
#include<bits/stdc++.h>
using namespace std;
struct juese{
unordered_set<string> op;//operations
unordered_set<string> tp;//types
unordered_set<string> tg;//targets
}tmp;
unordered_map<string,juese> v;
unordered_map<string,vector<string> > gl;
vector<string> groups;
bool ok(string name,string a,string b,string c){
for(auto i:gl[name])if((v[i].op.count(a)||v[i].op.count("*"))
&&(v[i].tp.count(b)||v[i].tp.count("*"))
&&(v[i].tg.count(c)||v[i].tg.empty())) return 1;
return 0;
}
int main(){
int n,m,q,tn;string s,t;
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>t;
cin>>tn;while(tn--){cin>>s;v[t].op.insert(s);}
cin>>tn;while(tn--){cin>>s;v[t].tp.insert(s);}
cin>>tn;while(tn--){cin>>s;v[t].tg.insert(s);}
}
for(int i=1;i<=m;i++){
cin>>s;
cin>>tn;
while(tn--){
cin>>t>>t;
gl[t].push_back(s);
}
}
for(int i=1;i<=q;i++){
bool f=0;
string a,b,c;
groups.clear();
cin>>s;
cin>>tn;
groups.push_back(s);
while(tn--){
cin>>t;
groups.push_back(t);
}
cin>>a>>b>>c;
for(auto j:groups){
if(ok(j,a,b,c)){
f=1;
break;
}
}
cout<<f<<endl;
}
return 0;
}
\(\Huge\text{CSP202209}\)
防疫大数据
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int r,m;
int a;
set<int> s[1005];
struct run{
int date;
int user;
int place;
int getdate;
}tmp;
struct my_cmp{
bool operator()(run a,run b){
return a.date>b.date;
}
};
priority_queue<run,vector<run>,my_cmp> q,p;
bool fk(int a,int dat,int tod){
if(dat<0) return 0;
for(int i=dat;i<=tod;i++) if(s[i].find(a)==s[i].end()) return 0;
return 1;
}
set<int> ans;
int main(){
cin>>n;
for(int t=0;t<n;t++){
ans.clear();
cin>>r>>m;
for(int i=1;i<=r;i++){
cin>>a;
for(int j=0;j<7;j++) s[t+j].insert(a);
}
for(int i=1;i<=m;i++){
cin>>tmp.date>>tmp.user>>tmp.place;
tmp.getdate=t;
q.push(tmp);
}
while(!q.empty()&&!(q.top().getdate>t-7&&q.top().date>t-7)) q.pop();
p=q;
while(!q.empty()){
tmp=q.top();
q.pop();
if(fk(tmp.place,tmp.date,t)){
ans.insert(tmp.user);
}
}
cout<<t<<" ";
for(auto i:ans) cout<<i<<" ";
cout<<endl;
q=p;
}
return 0;
}
\(\Huge\text{CSP202303}\)
田地丈量
代码
#include<bits/stdc++.h>
using namespace std;
int n;
long long a,b;
long long ans;
int main(){
cin>>n>>a>>b;
for(int i=1;i<=n;i++){
long long x,y,xx,yy;
cin>>x>>y>>xx>>yy;
x=max(x,0ll);y=max(y,0ll);
x=min(x,a);y=min(y,b);
xx=max(xx,0ll);yy=max(yy,0ll);
xx=min(xx,a);yy=min(yy,b);
ans+=(xx-x)*(yy-y);
}
cout<<ans;
return 0;
}
垦田计划
做法
二分。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int c[100005],t[100005];
bool check(int l){
long long sum=0;
for(int i=1;i<=n;i++){
if(t[i]>l) sum+=1ll*(t[i]-l)*c[i];
}
return sum<=m;
}
int main(){
cin>>n>>m>>k;
int l=k,r=0;
for(int i=1;i<=n;i++){
cin>>t[i]>>c[i];
if(t[i]>r) r=t[i];
}
int mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
LDAP
做法
模拟。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
#define N 2505
int dn[N];
map<int,set<pair<int,int> > > val;
string s;
int read(int& pos,int ed){int a=0;
for(;pos<ed&&s[pos]>='0'&&s[pos]<='9';pos++) a=a*10+s[pos]-48;
return a;
}
bitset<N> duan(int a,int b){
bitset<N> ans;
auto it1=val[a].lower_bound({b,0});
auto it2=val[a].lower_bound({b+1,0});
for(auto it=it1;it!=it2;it++) ans.set((*it).second);
return ans;
}
bitset<N> fanduan(int a,int b){
bitset<N> ans;
auto it1=val[a].lower_bound({b,0});
auto it2=val[a].lower_bound({b+1,0});
for(auto it=val[a].begin();it!=it1;it++) ans.set((*it).second);
for(auto it=it2;it!=val[a].end();it++) ans.set((*it).second);
return ans;
}
int pipei[2005];
void getpp(){
stack<int> st;
for(int i=0;i<s.length();i++){
pipei[i]=0;
if(s[i]=='(') st.push(i);
if(s[i]==')'){pipei[i]=st.top(),pipei[st.top()]=i;st.pop();}
}
}
bitset<N> expr(int i,int end){
if(s[i]>='0'&&s[i]<='9'){
int a=read(i,end);
char op=s[i++];
int b=read(i,end);
if(op==':') return duan(a,b);
else return fanduan(a,b);
}
bitset<N> x1=expr(i+2,pipei[i+1]);
bitset<N> x2=expr(pipei[i+1]+2,end-1);
return (s[i]=='&'?x1&x2:x1|x2);
}
int main(){
cin>>n;
for(int i=1,l,key,thi;i<=n;i++){
cin>>dn[i]>>l;
while(l--){
cin>>key>>thi;
val[key].insert({thi,i});
}
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>s;
getpp();
bitset<N> ans=expr(0,s.length());
set<int> aans;
for(int j=1;j<=n;j++) if(ans[j]) aans.insert(dn[j]);
for(auto x:aans) cout<<x<<" ";
cout<<"\n";
}
return 0;
}
星际网络 II
题面
详见我的博客中此题题解。
\(\Huge\text{CSP202305}\)
重复局面
做法
把每个状态压成一个字符串,然后扔到 map 里面。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
#define fi first
#define se second
#define endl '\n'
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define Cl(x) memset(x,0,sizeof(x))
const bool DC=0;
const ll mod=0;
const int N=0;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qpow(ll a,ll b,ll p=mod){ll ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
void NO(){cout<<"NO\n";}
void YES(){cout<<"YES\n";}
mt19937 rnd((unsigned long long)new char);
int n;
string s;
map<string,int>m;
void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
void __SOLVE__(int _case){
cin>>n;
while(n--){
string t;
int cnt=8;
s="";
while(cnt--)cin>>t,s+=t;
cout<<++m[s]<<endl;
}
}
int main(){/*freopen(".in","r",stdin);freopen(".out","w",stdout);*/__INIT__();int T;DC?cin>>T,1:T=1;for(int _CASE=1;_CASE<=T;_CASE++)__SOLVE__(_CASE);return 0;}
矩阵运算
做法
利用交换律乱斗顺序,把 nn 的矩阵换成 dd 的就可做了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
#define fi first
#define se second
#define endl '\n'
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define Cl(x) memset(x,0,sizeof(x))
const bool DC=0;
const ll mod=0;
const int N=0;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qpow(ll a,ll b,ll p=mod){ll ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
void NO(){cout<<"NO\n";}
void YES(){cout<<"YES\n";}
mt19937 rnd((unsigned long long)new char);
struct mat{
vector<vector<ll>>a;
mat(int r=0,int c=0){while(r--)a.push_back(vector<ll>(c,0));}
int r(){return a.size();}
int c(){return a[0].size();}
mat operator*(mat b){
const int n=r(),m=c(),p=b.r(),q=b.c();
mat ans(n,q);
for(int i=0;i<n;i++)for(int j=0;j<q;j++)for(int k=0;k<m;k++)ans.a[i][j]+=a[i][k]*b.a[k][j];
return ans;
}
mat operator+(mat b){
const int n=r(),m=b.c();
mat ans(n,c());
for(int i=0;i<n;i++)for(int j=0;j<c();j++)ans.a[i][j]=a[i][j]*b.a[0][i];
return ans;
}
mat T(){
int R=r(),C=c();
mat ans(C,R);
for(int i=0;i<R;i++)for(int j=0;j<C;j++)ans.a[j][i]=a[i][j];
return ans;
}
};
void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
void __SOLVE__(int _case){
int n,d;
cin>>n>>d;
mat Q(n,d),K(d,n),V(n,d),W(1,n);
for(int i=0;i<n;i++)for(int j=0;j<d;j++)cin>>Q.a[i][j];
for(int i=0;i<n;i++)for(int j=0;j<d;j++)cin>>K.a[j][i];
for(int i=0;i<n;i++)for(int j=0;j<d;j++)cin>>V.a[i][j];
for(int i=0;i<n;i++)cin>>W.a[0][i];
mat ans=(Q*(K*V))+W;
for(int i=0;i<n;i++,cout<<'\n')for(int j=0;j<d;j++)cout<<ans.a[i][j]<<' ';
}
int main(){/*freopen(".in","r",stdin);freopen(".out","w",stdout);*/__INIT__();int T;DC?cin>>T,1:T=1;for(int _CASE=1;_CASE<=T;_CASE++)__SOLVE__(_CASE);return 0;}
解压缩
做法
按题意模拟。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
#define fi first
#define se second
#define endl '\n'
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define Cl(x) memset(x,0,sizeof(x))
const bool DC=0;
const ll mod=0;
const int N=0;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qpow(ll a,ll b,ll p=mod){ll ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
void NO(){cout<<"NO\n";}
void YES(){cout<<"YES\n";}
mt19937 rnd((unsigned long long)new char);
struct B{
bitset<8>a;
B(int v=0){for(int cnt=0;v;v>>=1) a[cnt++]=v&1;}
bool operator[](const int b){return a[b];}
int v(int l=0,int r=7){int ans=0;for(int i=r;i>=l;i--)ans=ans*2+a[i];return ans;}
};
char d2h(int v){
assert(v<16);
if(v>9)return v-10+'a';
else return v+'0';
}
int h2d(char c){
if(c<='9')return c-48;
return c-97+10;
}
vector<B>s;
int n,cur,L;
vector<B>ans;
void huisu(int o,int l){
int p=ans.size();
int st=p-o;
for(int i=0;i<l;i++){
ans.push_back(ans[st]);
st++;
if(st==p)st=p-o;
}
}
void prt(int len){
while(len--)ans.push_back(s[cur++]);
}
void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
void __SOLVE__(int _case){
cin>>n;
for(int i=1;i<=n;i++){
char a,b;
cin>>a>>b;
s.push_back({h2d(a)*16+h2d(b)});
}
L=0;
while(s[cur][7]){
L+=s[cur].v(0,6)*pow(128,cur++);
}
L+=s[cur].v()*pow(128,cur++);
while(cur<s.size()){
B now=s[cur++];
if(now[0]==now[1]&&now[0]==0){
int len=now.v(2,7);
if(len>59){
int cnt=len-59;
int tmp=1;
len=0;
while(cnt--){
len+=tmp*s[cur++].v();
tmp*=256;
}
}
prt(len+1);
continue;
}
if(now[0]==1){
int o=now.v(5,7)*256+s[cur++].v();
int l=now.v(2,4);
huisu(o,l+4);
}else{
int l=now.v(2,7);
int o=s[cur+1].v()*256+s[cur].v();
cur+=2;
huisu(o,l+1);
}
}
int cnt=0;
for(auto i:ans){
cout<<d2h(i.v(4,7))<<d2h(i.v(0,3));
if(++cnt%8==0)cout<<'\n';
}
cout<<endl;
}
int main(){/*freopen(".in","r",stdin);freopen(".out","w",stdout);*/__INIT__();int T;DC?cin>>T,1:T=1;for(int _CASE=1;_CASE<=T;_CASE++)__SOLVE__(_CASE);return 0;}
电力网络
做法
五个 subtask 做法不同。首先有一个极其简单的树形 dp:fij 表示 i 在颜色为 j 时的最小花费。
- 爆搜。
- 树的情况直接用上述 dp。
- 基环树的情况,先把所有子树的结果缩成一个点,剩余的环直接选任意一个点枚举其颜色,dp 一圈回来。
- 找 D 可以看度数恰好为 \(n-m+1\) 的点且连接的点度数为 \(2\),树形 dp 的时候注意不要 dfs 到 D 。
- 把所有链缩成一条边或缩回对应的度数 >2 的点,之后继续爆搜。
超时了两个点,尽力了
代码
略。
闪耀巡航
做法
考虑拆点,每个点拆成 1024 个不同状态,之后乱斗建图跑最短路。
每条边的答案为它自身的长度加从终点(状态为这个串满足的状态)走到起点(状态为满)的最短路。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
#define fi first
#define se second
#define endl '\n'
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define Cl(x) memset(x,0,sizeof(x))
const bool DC=0;
const ll mod=0;
const int N=0;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qpow(ll a,ll b,ll p=mod){ll ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
void NO(){cout<<"NO\n";}
void YES(){cout<<"YES\n";}
mt19937 rnd((unsigned long long)new char);
int n;
string t,s[100005];
bool cnt[135];
struct edge{int from,to,len,cg;};
vector<edge>v[35];
int f[35][28005];
priority_queue<pii>q;
bool vis[28005];
void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
void dij(int st){
memset(vis,0,sizeof(vis));
f[st][st*1024]=0;
q.push({0,st*1024});
while(!q.empty()){
int now=q.top().second;
q.pop();
if(vis[now])continue;
vis[now]=1;
int c=now/1024,sta=now%1024;
for(auto i:v[c]){
int to=i.to*1024+(sta|i.cg);
if(f[st][to]>f[st][now]+i.len){
f[st][to]=f[st][now]+i.len;
q.push({-f[st][to],to});
}
}
}
}
void __SOLVE__(int _case){
cin>>n>>t;
for(int i=1;i<=n;i++){
cin>>s[i];
for(auto j:s[i])cnt[j]=1;
int cg=0;
for(int j=0;j<t.size();j++)if(cnt[t[j]])cg|=(1<<j),cnt[t[j]]=0;
v[s[i][0]-96].push_back({s[i][0]-96,s[i].back()-96,s[i].size()-1,cg});
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=26;i++)dij(i);
for(int i=1;i<=n;i++){
for(auto j:s[i])cnt[j]=1;
int cg=0;
for(int j=0;j<t.size();j++)if(cnt[t[j]])cg|=(1<<j),cnt[t[j]]=0;
int ans=0x3f3f3f3f;
int sb=(1<<t.size());
for(int j=0;j<sb;j++){
if((j|cg)==sb-1){
ans=min(ans,(int)s[i].size()-1+f[s[i].back()-96][(s[i][0]-96)*1024+j]);
}
}
if(ans==0x3f3f3f3f)ans=-1;
cout<<ans<<endl;
}
}
int main(){/*freopen(".in","r",stdin);freopen(".out","w",stdout);*/__INIT__();int T;DC?cin>>T,1:T=1;for(int _CASE=1;_CASE<=T;_CASE++)__SOLVE__(_CASE);return 0;}
\(\Huge\text{CSP202309}\)
坐标变换(其一)
做法
直接记录一下所有操作总共加了多少。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll mod=0;
struct point{
long long x,y;
point operator +(point b){
point ans;
ans.x=x+b.x;
ans.y=y+b.y;
return ans;
}
point operator -(point b){
point ans;
ans.x=x-b.x;
ans.y=y-b.y;
return ans;
}
}a[1005],tmp,add;
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>tmp.x>>tmp.y;
add=add+tmp;
}
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y;
a[i]=a[i]+add;
}
for(int i=1;i<=m;i++)cout<<a[i].x<<" "<<a[i].y<<endl;
return 0;
}
坐标变换(其二)
做法
两种操作不会互相影响,因此分开做前缀和。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll mod=0;
struct point{
double x,y;
point operator +(point b){
point ans;
ans.x=x+b.x;
ans.y=y+b.y;
return ans;
}
point operator -(point b){
point ans;
ans.x=x-b.x;
ans.y=y-b.y;
return ans;
}
point operator *(double ang){
double ca=cos(ang),sa=sin(ang);
point ans;
ans.x=x*ca-y*sa;
ans.y=y*ca+x*sa;
return ans;
}
bool operator ==(point b){
return (x==b.x)&&(y==b.y);
}
bool operator <(point b){
return (y==b.y)?(x<b.x):(y<b.y);
}
}tmp;
double tp1[100005],tp2[100005];
int n,m;
int main(){
cin>>n>>m;
tp1[0]=1;
for(int i=1;i<=n;i++){
double tmp;
int tp;
cin>>tp>>tmp;
tp1[i]=tp1[i-1];
tp2[i]=tp2[i-1];
if(tp==1)tp1[i]*=tmp;
else tp2[i]+=tmp;
}
for(int i=1;i<=m;i++){
int l,r;
double x,y;
cin>>l>>r>>x>>y;
tmp={x*tp1[r]/tp1[l-1],y*tp1[r]/tp1[l-1]};
tmp=tmp*(tp2[r]-tp2[l-1]);
printf("%.3lf %.3lf\n",tmp.x,tmp.y);
}
return 0;
}
梯度求解
题面
见我的博客中此题题解。
阴阳龙
题面
见我的博客中此题题解。