9[CSP-J2019] 加工零件
思路：题目要求的是1和a之间是否有长度为l的路径，如果3到1有长度为5的路径，那么3到1一定有长度为7的路径，但并不一定有长度为6的路径。所以，我们要对每个点求一遍奇数路径，和偶数路径。
#include<bits/stdc++.h>
using namespace std;
vector<int> c[1000010];
int ou[1000010];//ou[i]表示到i之间的最短偶数路径数
int ji[1000010];//ji[i]表示到i之间的最短奇数路径数
struct node{
int a,cnt;
};
void bfs(){
//初始最大值
memset(ou,0x3f,sizeof(ou));
memset(ji,0x3f,sizeof(ji));
queue<node> q;
q.push({1,0});
//如果有独立节点，要将所有独立节点标记自己到自己的路径为1
for(int i=0;i<c[1].size();i++){
ji[c[1][i]]=1;
q.push({c[1][i],1});
}
while(!q.empty()){
node k=q.front();
q.pop();
for(int i=0;i<c[k.a].size();i++){
if(k.cnt%2==1){
//如果1到当前节点的路径数为奇数，那么到下一个节点的路径数为偶数
if(k.cnt+1<ou[c[k.a][i]]){
ou[c[k.a][i]]=k.cnt+1;
q.push({c[k.a][i],k.cnt+1});
}
}else{
//如果1到当前节点的路径数为偶数，那么到下一个节点的路径数为奇数
if(k.cnt+1<ji[c[k.a][i]]){
ji[c[k.a][i]]=k.cnt+1;
q.push({c[k.a][i],k.cnt+1});
}
}
}
}
}
int main(){
//freopen("work.in","r",stdin);
//freopen("work.out","w",stdout);
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
//题目图例说明是双向图
c[u].push_back(v);
c[v].push_back(u);
}
bfs();
while(q--){
int a,l;
cin>>a>>l;
//判断l是否为奇偶数
if(l%2==0){
//如果1到a的偶数路径>l
//说明不可能存在1到a有长度为l的偶数路径
if(ou[a]>l){
cout<<"No"<<'\n';
}else{
cout<<"Yes"<<'\n';
}
}else{
//如果1到a的奇数路径>l
//说明不可能存在1到a有长度为l的奇数路径
if(ji[a]>l){
cout<<"No"<<'\n';
}else{
cout<<"Yes"<<'\n';
}
}
}
return 0;
}
10[CSP-J2019] 公交换乘
思路：用数组模拟队列存储做地铁时获得的优惠券，可以做到使用获得时间最早的优惠券，但是要记得将时间失效的券淘汰掉，否则每次遍历数组会MLE
#include<bits/stdc++.h>
using namespace std;
struct node{
long long money,times;
};
node que[100010];
int tot=0,tai=1;
//tot表示队列队尾，tai表示队列队头
bool vis[100010];
int main(){
//freopen("transfer.in","r",stdin);
//freopen("transfer.out","w",stdout);
int n;
cin>>n;
long long cnt=0;
for(int i=1;i<=n;i++){
int op,price,t;
cin>>op>>price>>t;
//坐地铁时直接cnt+=price
if(op==0){
cnt+=price;
que[++tot].times=t+45;
que[tot].money=price;
}else{
bool k=false;
while(tai<tot&&que[tai].times<t){
tai++;
} //淘汰掉时间失效的券 (wuwuwuwuwu)
for(int j=tai;j<=tot;j++){
//可以用的优惠券满足没被使用过,公交车钱不超过地铁票价，时间有效等要求
if(vis[j]!=1&&price<=que[j].money&&t<=que[j].times){
vis[j]=1;
k=true;
//使用最早获得的券，马上结束
break;
}
}
if(k==false){
cnt+=price;
}
}
}
cout<<cnt;
return 0;
}
11[CSP-J 2021] 插入排序
思路1：题目限制修改次数<=5000，所以O(nq)的时间复杂度可以过，可以在每次单点修改后前后冒泡各一次来保持有序，在维护一个有序序列，并记录原下标与先下标之间的关系（用数组记录），每次修改后更新这种关系。
#include<bits/stdc++.h>
using namespace std;
struct node{
int w,id;
};
bool cnp(node a,node b) {
if(a.w!=b.w){
return a.w<b.w;
}
return a.id<b.id;
}
node a[100010];
int t[100010];//t[i]表示在原数组a中下标为i的数在新序列中的位置(下标)
int main(){
//freopen("sort.in","r",stdin);
//freopen("sort.out","w",stdout);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i].w;
a[i].id=i;
}
sort(a+1,a+1+n,cnp);
//第一次统计第一次排序后的位置
for(int i=1;i<=n;i++){
t[a[i].id]=i;
}
for(int i=1;i<=q;i++){
int o;
cin>>o;
if(o==1){
int x,v;
cin>>x>>v;
//题意为修改a[x]为v，但x的下标为原数组t[x]
a[t[x]].w=v;
for(int j=n;j>=2;j--){
if(cnp(a[j],a[j-1])){
node k=a[j-1];
a[j-1]=a[j];
a[j]=k;
}
}
for(int j=2;j<=n;j++){
if(cnp(a[j],a[j-1])){
node k=a[j-1];
a[j-1]=a[j];
a[j]=k;
}
}
for(int j=1;j<=n;j++){
t[a[j].id]=j;
}
}else{
int x;
cin>>x;
cout<<t[x]<<'\n';
}
}
return 0;
}
思路2：对于每个修改操作，我们直接修改。对于每个查询操作，我们暴力查询，从头向后查找，按题意模拟即可。
#include<iostream>
#include<cstdio>
using namespace std;
int a[10011];
int main()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=q;i++){
int xx;
scanf("%d",&xx);
if(xx==1){
int x,v;
scanf("%d%d",&x,&v);
a[x]=v;
}
else {
int x;
scanf("%d",&x);
int w=a[x];
int sum=n;//初始化x在a=[n](新数组最后一位)
for(int j=1;j<x;j++){//前1->x-1位
if(a[j]>w){
sum--;//统计比w小的(可以往前多少位)
}
}
for(int j=x+1;j<=n;j++){//后x+1->n位
if(a[j]>=w) sum--;//统计比w小的(可以往前少位)
}
printf("%d\n",sum);
}
}
return 0;
}
12[CSP-J 2021] 网络连接
思路：判断ERR的函数细节超级多，非常烦人，判断地址是否重复可以用map或set，豆肥肠刻意
#include<bits/stdc++.h>
using namespace std;
map<string,long long> mp;
bool check(string h){
int cnt1=0,cnt2=0,cnt3=0,len=h.size();
//cnt1统计'.'个数，cnt2统计':'个数，cnt3统计数字个数
long long tmp=0;
//tmp记录数字大小
for(int i=0;i<len;i++){
if((i==0||(h[i-1]=='.'||h[i-1]==':'))&&h[i]>='0'&&h[i]<='9'){
cnt3++;
}
if(h[i]=='.'||h[i]==':'){
if(h[i]=='.')cnt1++;
else cnt2++;
if(cnt1<3&&cnt2!=0||cnt3==0)return false;
//判断符合顺序是否正确，例如a:b.c.d.e或.a.b.c:df
if(tmp<0||tmp>255)return false;
//例如256.233.244.12：556
else{tmp=0;continue;}
}else if(h[i]<'0'||h[i]>'9') return false;//出现了奇怪的字符
if(i!=0&&tmp==0&&h[i-1]=='0') return false;//判断前导 0
tmp = tmp*10+h[i]-'0';
}
if(cnt1!=3||cnt2!=1||cnt3!=5)return false;//判断各个字符数量是否合法
if(tmp<0||tmp>65535)return false;//判断最后一位(e)是否合法
else return true;
}
int main(){
//freopen("network.in","r",stdin);
//freopen("network.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
string a,h;
cin>>a>>h;
if(!check(h)){
cout<<"ERR"<<'\n';
}else if(a=="Server"){
if(mp[h]==0){
cout<<"OK"<<'\n';
mp[h]=i;
}else cout<<"FAIL"<<'\n';
}else{
if(mp[h]==0){
cout<<"FAIL"<<'\n';
}else cout<<mp[h]<<'\n';
}
}
return 0;
}
极致压行&&美观性版
#include<bits/stdc++.h>
using namespace std;
map<string,long long> mp;
bool check(string h){
int cnt1=0,cnt2=0,cnt3=0,len=h.size();long long tmp=0;
for(int i=0;i<len;i++){
if((i==0||(h[i-1]=='.'||h[i-1]==':'))&&h[i]>='0'&&h[i]<='9')cnt3++;
if(h[i]=='.'||h[i]==':'){
if(h[i]=='.')cnt1++;
else cnt2++;
if(cnt1<3&&cnt2!=0||cnt3==0)return false;
if(tmp<0||tmp>255)return false;
else{tmp=0;continue;}
}else if(h[i]<'0'||h[i]>'9') return false;
if(i!=0&&tmp==0&&h[i-1]=='0') return false;
tmp=tmp*10+h[i]-'0';
}
if(cnt1!=3||cnt2!=1||cnt3!=5||tmp<0||tmp>65535)return false;
else return true;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
string a,h;
cin>>a>>h;
if(!check(h))cout<<"ERR"<<'\n';
else if(a=="Server"){
if(mp[h]==0){cout<<"OK"<<'\n';mp[h]=i;}
else cout<<"FAIL"<<'\n';
}else{
if(mp[h]==0)cout<<"FAIL"<<'\n';
else cout<<mp[h]<<'\n';
}
}
return 0;
}
13[CSP-J 2021] 小熊的果篮
思路：用链表连接每一个水果，好处是删除元素很方便，统计“块”可以用vector维护每一个“块”的最左边元素。
#include<bits/stdc++.h>
using namespace std;
bool vis[1000010];
struct node{
int x,nxt,pre;
};
node a[200010];//数组模拟链表
vector<int> now;//维护每一个"块"的最左边的数
//链表删除操作
void shanchu(int x){
int p1=a[x].pre,p2=a[x].nxt;
a[p1].nxt=p2;
a[p2].pre=p1;
}
int main(){
//关闭流同步，加快代码运行时间
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
int n;
cin>>n;
a[0].nxt=1;//用0做假对头，方便遍历
a[0].x=a[n+1].x=INT_MAX;//因为是假元素，所以赋值INT_MAX
for(int i=1;i<=n;i++){
cin>>a[i].x;
//
if(a[i].x!=a[i-1].x){
now.push_back(i);
}
a[i].pre=i-1;
a[i].nxt=i+1;
}
while(a[0].nxt<=n){
vector<int> tmp;//统计遍历完后的“块”的最左边数
for(int i=0;i<now.size();i++){
int xs=now[i];
cout<<xs<<" ";
shanchu(xs);
//判断x的下一个元素是否为块的最左边元素，要满足x的前一个数不等于x的后一个数(因为x已被删除)，并且当前删除元素要等与下一个元素
//举例：n=12
//a[1->12]={1 1 0 0 1 1 1 0 1 1 0 0}
// 要删除第三个数，它是“块”的最左边元素，它下一个元素!=它前一个元素，所以，第四个元素是新“块”的新的最左边。
if(a[a[xs].pre].x!=a[a[xs].nxt].x&&a[xs].x==a[a[xs].nxt].x){
tmp.push_back(a[xs].nxt);
}
}
cout<<'\n';
now=tmp;
}
return 0;
}
14[CSP-J2020] 表达式(未完成)
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int son[100005][2];
int flag[1000010];
int dfs(int u,int g){
a[u]^=g;
if(u<=n){
return a[u];
}
}
void dfs2(int u){
if(u>=n)return ;
c[son[u][1]]|=c[u];
c[son[u][0]]|=c[u];
dfss(son[u][0]);
dfss(son[u][1]);
}
int main(){
//freopen("expr.in","r", stdin);
//freopen("expr.out","w",stdout);
string s;
getline(cin,s)
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
stack<int> bs;
int ck=n;
for(int i=0;i<s.size();i+=2){
//统计编号(x1,x2,x3...)
if(s[i]=='x'){
int x=0;
i++;
while(s[i]!=' '){
x=x*10+s[i]-'0';
i++;
}
i--;
b.push(x);
}else if(s[i]=='&'){
int x=b.top();
b.pop();
int y=b.top();
b.push(++ck);
a[ck]=2;
//建立字符树
son[ck][0]=x;//
son[ck][1]=y;//
}else if(s[i]=='|'){
int x=b.top();
b.pop();
int y=b.top();
b.push(++ck);
a[ck]=3;
son[ck][0]=x;
son[ck][0]=y;
}else{
flag[b.top()]^=1;
}
}
int ans=dfs(ck,flag[ck]);
dfs2(ck);
int q;
cin>>q;
for(int i=1;i<=q;i++){
int t;
cin>>t;
if(c[t]){
cout<<ans<<'\n';
}else{
cout<<!ans<<'\n';
}
}
return 0;
}
C24zhaozicheng
LV 10
@
2025-10-8 16:13:06