CSPJ2019A. 数字游戏 (Number Games)

00010100 

2

数据范围与提示

对于 $20\%$ 的数据，保证输入的字符全部为 $0$。

对于 $100\%$ 的数据，输入只可能包含字符 $0$ 和字符 $1$，字符串长度固定为 $8$。

#include<bits/stdc++.h>
using namespace std;
long long q,w,e,r,t,y,u,i,o,p,s,d,f,g,h,j,k,l,m,n,v,x,z,kk;
int b[1000];
int a[1000];
int c[1000];
char cc;
int main()
{
	for(i=1;i<=8;i++)
	{
		cin>>cc;
		if(cc=='1')
		k++;
	}
	cout<<k;
	return 0;
}

CSPJ2019B 公交换乘 (Bus Transfer)

6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135

36

第一条记录，在第 3 分钟花费 10 元乘坐地铁。

第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。

第三条记录，在第 50 分种花费 12 元乘坐地铁。

第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45分钟，所以优惠票已失效，花费 3 元乘坐公交车。

第五条记录，在第 110 分钟花费 5 元乘坐地铁。

第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票，花费 6 元乘坐公交车。

总共花费 36 元。

6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68

32

第一条记录，在第 1 分钟花费 5 元乘坐地铁。

第二条记录，在第 16 分钟花费 20 元乘坐地铁。

第三条记录，在第 23 分钟花费 7 元乘坐地铁。

第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。

第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。

第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。

总共花费 32 元。

数据范围与提示

对于 $30\%$ 的数据，$n\le 1000$，ti≤106t_i \le 10^6ti​≤106。
另有 $15\%$ 的数据，ti≤107t_i \le 10^7ti​≤107，priceiprice_ipricei​都相等。
另有 $15\%$ 的数据，ti≤109t_i \le 10^9ti​≤109，priceiprice_ipricei​都相等。
对于 $100\%$ 的数据，n≤105n \le 10^5n≤105，ti≤109t_i \le 10^9ti​≤109，1≤pricei≤10001 \le price_i \le 10001≤pricei​≤1000。

#include<bits/stdc++.h>
using namespace std;
int opt,n,t[100001],p[100001],ans,top,m=1,yh[100001],sj[100001],k;
bool r[100001];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>opt>>p[i]>>t[i];
		if(opt==0) yh[++top]=p[i],sj[top]=t[i],ans+=p[i];
		else{
			k=0;
			for(int j=m;j<=top;j++){
				if(r[j]) continue;
				if(t[i]-sj[j]>45) m=j;
				else if(yh[j]>=p[i]){
					k=j;
					r[k]=true;
					break;
				}
			}
			if(!k) ans+=p[i];
		}
	}///test
	cout<<ans;
}

CSPJ2019C. 纪念品 (Souvenir)

6 1 100
50
20
25
20
25
50

305

最佳策略是：

第二天花光所有 $100$ 枚金币买入 $5$ 个纪念品 $1$；
第三天卖出 $5$ 个纪念品 $1$，获得金币 $125$ 枚；
第四天买入 $6$ 个纪念品 $1$，剩余 $5$ 枚金币；
第六天必须卖出所有纪念品换回 $300$ 枚金币，第四天剩余 $5$ 枚金币，共 $305$ 枚金币。

超能力消失后，小伟最多拥有 $305$ 枚金币。

3 3 100
10 20 15
15 17 13
15 25 16

217

最佳策略是：

第一天花光所有金币买入 $10$ 个纪念品 $1$；
第二天卖出全部纪念品 $1$ 得到 $150$ 枚金币并买入 $8$ 个纪念品 $2$ 和 $1$ 个纪念品 $3$，剩余 $1$ 枚金币；
第三天必须卖出所有纪念品换回 $216$ 枚金币，第二天剩余 $1$ 枚金币，共 $217$ 枚金币。

超能力消失后，小伟最多拥有 $217$ 枚金币。

数据范围与提示

对于 $10\%$ 的数据，$T=1$。
对于 $30\%$ 的数据，$T\le 4,N\le 4,M\le 100$，所有价格 10≤Pi,j≤100110 \le P_{i,j} \le 100110≤Pi,j​≤1001 。
另有 $15\%$ 的数据，$T\le 100,N=1$。
另有 $15\%$ 的数据，$T=2,N\le 100$。
对于 $100\%$ 的数据，T≤100,N≤100,M≤103T \le 100, N \le 100, M \le 10^3T≤100,N≤100,M≤103，所有价格 1≤Pi,j≤1041 \le P_{i,j} \le 10^4 1≤Pi,j​≤104，数据保证任意时刻，小明手上的金币数不可能超过 10410^4104。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int MAXN = 105;

//dp[k]表示手里剩k元现金的时候，明天早上都卖了以后的钱数
//price[i][j]表示第i天第j件物品的价格
int dp[10005], price[MAXN][MAXN];

int main() {
    int t, n, m, ans;
    scanf("%d%d%d", &t, &n, &m);
    //先输入
    for (int i = 1; i <= t; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &price[i][j]);
        }
    }
    //第一天早上手里有m元
    ans = m;
    for (int i = 1; i < t; ++i) {
        //先把数组赋值为负无穷
        memset(dp, ~0x3f, sizeof(dp));
        //什么都不买，今天早上有ans元，明天早上也是ans元
        dp[ans] = ans;
        //枚举第j个物品
        for (int j = 1; j <= n; ++j) {
            //手里有k元的时候，去推明天早上的钱
            for (int k = ans; k >= price[i][j]; --k) {
                //买一件物品，现金减少，赚一份差价，完全背包倒着循环
                dp[k - price[i][j]] = max(dp[k - price[i][j]], dp[k] + price[i + 1][j] - price[i][j]);
            }
        }
        //找一下明天早上收益最大
        int ma = 0;
        for (int j = 0; j <= ans; ++j) {
            ma = max(ma, dp[j]);
        }
        //明天早上就有这么多钱了，继续赚钱
        ans = ma;
    }
    cout << ans << endl;
    return 0;
}

CSPJ2019D. 零件加工 (Parts Processing)

3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2

No
Yes
No
Yes
No
Yes

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 2 的工人想生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

编号为 3 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

编号为 2 的工人想生产第 2 阶段的零件，需要编号为 1 和 3 的工人生产第 1 阶段的零件，他/她们都需要编号为 2 的工人提供原材料。

编号为 3 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

5 5 5
1 2
2 3
3 4
4 5
1 5
1 1
1 2
1 3
1 4
1 5

No
Yes
No
Yes
Yes

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 和 5 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 和 5 的工人生产第 1 阶段的零件，需要编号为 1,3,4 的工人提供原材料。

编号为 1 的工人想生产第 3 阶段的零件，需要编号为 2 和 5 的工人生产第 2 阶段第10页共10页的零件，需要编号为 1,3,4 的工人生产第 1 阶段的零件，需要编号为 2,3,4,5 的工人提供原材料。

编号为 1 的工人想生产第 4 阶段的零件，需要编号为 2 和 5 的工人生产第 3 阶段的零件，需要编号为 1,3,4 的工人生产第 2 阶段的零件，需要编号为 2,3,4,5 的工人生产第 1 阶段的零件，需要全部工人提供原材料。

编号为 1 的工人想生产第 5 阶段的零件，需要编号为 2 和 5 的工人生产第 4 阶段的零件，需要编号为 1,3,4 的工人生产第 3 阶段的零件，需要编号为 2,3,4,5 的工人生产第 2 阶段的零件，需要全部工人生产第 1 阶段的零件，需要全部工人提供原材料。

数据范围与提示

共 $20$ 个测试点。

• $1\le u,v,a\le n$

测试点 $1\sim 4$ , $1\le n,m\le 1000,q=3，L=1$。

测试点 $5\sim 8$ , $1\le n,m\le 1000,q=3，1\le L\le 10$。

测试点 $9\sim 12$ , $1\le n,m,L\le 1000,1\le q\le 100$

测试点 $13\sim 16$, 1≤n,m,L≤1000,1≤q≤1051 \le n, m, L \le 1000, 1 \le q \leq 10^51≤n,m,L≤1000,1≤q≤105

测试点 $17\sim 20$, 1≤n,m,q≤105,1≤L≤1091 \le n, m, q \le 10^5 , 1 \le L \leq 10^91≤n,m,q≤105,1≤L≤109 。

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
template<typename T>void write(T x){
	if(x<0)putchar('-'),x*=-1;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
vector<int>v[100010];
int ji[100010],ou[100010];
void bfw(){//我有一个好朋友叫bfw，所以我写bfs时，喜欢把函数名起为bfw
	memset(ji,0x3f,sizeof(ji));//奇数最短路径
	memset(ou,0x3f,sizeof(ou));//偶数最短路径
	queue<pair<int,int> >q;
	for(int i=0;i<v[1].size();i++){
		ji[v[1][i]]=1;
		q.push(make_pair(v[1][i],1));
	}
	while(q.size()){
		int x=q.front().first,y=q.front().second;
		for(int i=0;i<v[x].size();i++){
			if(y%2==1){//奇数+1=偶数
				if(y+1<ou[v[x][i]]){
					ou[v[x][i]]=y+1;//更新答案
					q.push(make_pair(v[x][i],y+1));
				}
			}else{//偶数+1=奇数
				if(y+1<ji[v[x][i]]){
					ji[v[x][i]]=y+1;//更新答案
					q.push(make_pair(v[x][i],y+1));
				}
			}
		}
		q.pop();
	}
}
int main(){
	int n,m,q;
	read(n);read(m);read(q);
	for(int i=1;i<=m;i++){
		int x,y;
		read(x);read(y);//无向边
		v[x].push_back(y);//连边
		v[y].push_back(x);//连边
	}
	bfw();//跑最短路
	while(q--){
		int x,y;
		read(x);read(y);
		if(y%2==0){
			if(ou[x]>y)puts("No");//如果大于就不可能了
			else puts("Yes");
		}else{
			if(ji[x]>y)puts("No");//如果大于就不可能了
			else puts("Yes");
		}
	}
	return 0;
}