ABC060

[ABC060B] Choose Integers

题面翻译

问在A的倍数里有没有除B余C的，如果有输出"YES"(双引号不输出)，否则输出"NO"(双引号不输出)

题目描述

あなたは、正の整数をいくつか選び、それらの総和を求めます。

選ぶ数の上限や、選ぶ整数の個数に制限はありません。どんなに大きな整数を選んでもよいですし、整数を $ 5000 $ 兆個選んでもよいです。ただし、選ぶ数はすべて $ A $ の倍数でなくてはいけません。また、少なくとも $ 1 $ つは整数を選ばなくてはいけません。

そして総和を $ B $ で割ったあまりが $ C $ となるようにしたいです。こうなるように整数を選ぶことが出来るか判定してください。

出来るならば YES、そうでないならば NO を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ A $ $ B $ $ C $

输出格式

YES か NO を出力する。

样例 #1

样例输入 #1
7 5 1
样例输出 #1
YES
样例 #2

样例输入 #2
2 2 1
样例输出 #2
NO
样例 #3

样例输入 #3
1 100 97
样例输出 #3
YES
样例 #4

样例输入 #4
40 98 58
样例输出 #4
YES
样例 #5

样例输入 #5
77 42 36
样例输出 #5
NO
提示

制約

$ 1 ≦ A ≦ 100 $

$ 1 ≦ B ≦ 100 $

$ 0 ≦ C $

Sample Explanation 1

たとえば $ 7, 14 $ を選ぶと総和は $ 21 $ となり、これを $ 5 $ で割ったあまりは $ 1 $ となります。

Sample Explanation 2

偶数をいくつ足したとしても、けっして奇数になることはありません。

Sample Explanation 3

$ 1 $ の倍数、つまりすべての整数が選べるので、$ 97 $ を選べば良いです。

思路

比较常见的解法就是从1开始枚举，直到b。因为$a*(b+k)\ mod\ b=0$一定成立。

#include<bits/stdc++.h>//万能头文件可好 
using namespace std;
int main(){//主函数 
	int a,b,c;//定义 
	scanf("%d%d%d",&a,&b,&c);//输入 
	for(int i=1;i<=b;i++){//开始循环判断，前文有解释 
		if((a*i)%b==c){//若符合题意 
			printf("YES\n");//输出，换行是个好习惯 
			return 0;//提前结束程序 
		}
	}
	printf("NO\n");//如果一直没有符合题意的倍速，则输出NO 
	return 0;//over~
}

还有一种比较有趣的解法（来自：题解 AT2554 【Choose Integers】 - 洛谷专栏 (luogu.com.cn)）

#include<bits/stdc++.h>

using namespace std;

int gcd(int x , int y){//最大公约数函数
	while(x % y){//更相减损法进阶：辗转相除法
		int r = x % y;//取余
		x = y;
		y = r;//迭代
	}
	return y;//最大公约数
}

int main(){
	
	int a , b , c;
	cin >> a >> b >> c;//被除数，除数，余数
	
	if(c % gcd(a , b) == 0){//这条式子下面会给出证明
		cout << "YES";
	}else{
		cout << "NO";
	}
	return 0;
}

证明

//证明：
//原题可表示为 
//k * a - p * b = c
//原式 = gcd(a , b) * [k * a / gcd(a , b) - p * b / gcd(a , b)]
//因为 k , p为任意整数
//所以 [k * a / gcd(a , b) - p * b / gcd(a , b)] 可以取任意整数值
//所以当 c 能整除 gcd(a , b)时 , 可以满足题目条件

[ABC060C] Sentou

题面翻译

题目描述

在一个公共澡堂里，有一个淋浴器。在按下开关时，淋浴器将会开始运作，在 $T$ 秒内一直流出热水。

如果你在淋浴器运作的情况下时按下开关，水就会从当前时间开始继续运作 $T$ 秒，而不是让淋浴器多运作 $T$ 秒。

在这个淋浴间前，有 $N$ 个人按下开关。第 $i$ 个人在第 $1$ 个人按下开关后的第 $t_i$ 个秒按下开关。请求出淋浴器运作的总时间。

输入格式

第一行两个整数 $N$ 和 $T$，分别表示人数和淋浴器连续工作时间。

第二行共 $N$ 个整数，第 $i$ 个整数代表 $t_i$，含义见题目描述。

输出格式

一行一个整数，淋浴器运作的总时间。

数据范围

$ 1  N  200,000 $

$ 1  T  10^9 $

$ 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N  10^9 $

$ T $ 和 $ t_i $ 都是整数。

题目描述

とある銭湯には、スイッチを押すと $ T $ 秒間お湯が出るシャワーがあります。

なお、お湯が出ているときにスイッチを押すと、そのタイミングから $ T $ 秒間お湯が出つづけます。お湯の出る時間が $ T $ 秒間延長されるわけではないことに注意してください。

このシャワーの前を、$ N $ 人の人がスイッチを押して通り過ぎていきます。 $ i $ 人目の人は、$ 1 $ 人目の人がスイッチを押した $ t_i $ 秒後にスイッチを押します。

お湯が出る時間の総和は何秒かを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ T $ $ t_1 $ $ t_2 $ ... $ t_N $

输出格式

お湯が出る時間の総和を $ X $ 秒として、$ X $ を出力する。

样例 #1

样例输入 #1
2 4
0 3
样例输出 #1
7
样例 #2

样例输入 #2
2 4
0 5
样例输出 #2
8
样例 #3

样例输入 #3
4 1000000000
0 1000 1000000 1000000000
样例输出 #3
2000000000
样例 #4

样例输入 #4
1 1
0
样例输出 #4
1
样例 #5

样例输入 #5
9 10
0 3 5 7 100 110 200 300 311
样例输出 #5
67
提示

制約

$ 1 ≦ N ≦ 200,000 $

$ 1 ≦ T ≦ 10^9 $

$ 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≦ 10^9 $

$ T, t_i $ はすべて整数である

Sample Explanation 1

$ 1 $ 人目の人がスイッチを押し、お湯が $ 3 $ 秒出た後にもう一度スイッチが押され、$ 4 $ 秒間お湯が出続けます。よって合計で $ 7 $ 秒間お湯が出ます。

Sample Explanation 2

$ 1 $ 人目の人がスイッチを押して、お湯が出終わった $ 1 $ 秒後にもう一度スイッチが押されます。

思路

只要判断这段时间段内是否重合即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
ll a[MAXN];
int main(){
    ios::sync_with_stdio(false);
    ll n,t;cin>>n>>t;
    ll ans=t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        //重合了，更新加上差值
        if(a[i]+t>a[i+1]){
            ans+=a[i+1]-a[i];
        }
        //没有重合，加上t
        else{
            ans+=t;
        }
    }
    cout<<ans;
    return 0;
}

[ABC060D] Simple Knapsack

题面翻译

你有 $N$ 个物品和容量为 $W$ 的背包，每个物品要么选要么不选,它们的体积为 $w_i$，价值为 $v_i$，求总体积至多为 $W$ 情况下能拿走物品价值的最大值。

【数据范围】

$1\le N \le 100$，$1\le W \le 10^9$，$1 \le w_i \le 10^9$
$w_1 \le w_i \le w_1+3 (i=2,3,\cdots N)$
$1 \le v_i \le 10^7$
$W,w_i,v_i$ 都是整数

翻译：So_what

题目描述

あなたは $ N $ 個の物と、強度 $ W $ のバッグを持っています。 $ i $ 個目の物は、重さが $ w_i $ で価値が $ v_i $ です。

あなたは、物のうちいくつかを選び、バッグに入れます。ただし、選んだ物の重さの和は $ W $ 以下でなくてはいけません。

あなたは、バッグに入れた物の価値の総和を最大化したいです。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ : $ w_N $ $ v_N $

输出格式

価値の総和の最大値を出力する。

样例 #1

样例输入 #1
4 6
2 1
3 4
4 10
3 4
样例输出 #1
11
样例 #2

样例输入 #2
4 6
2 1
3 7
4 10
3 6
样例输出 #2
13
样例 #3

样例输入 #3
4 10
1 100
1 100
1 100
1 100
样例输出 #3
400
样例 #4

样例输入 #4
4 1
10 100
10 100
10 100
10 100
样例输出 #4
0
提示

制約

$ 1 ≦ N ≦ 100 $

$ 1 ≦ W ≦ 10^9 $

$ 1 ≦ w_i ≦ 10^9 $

すべての $ i = 2,3,...,N $ について、$ w_1 ≦ w_i ≦ w_1 + 3 $

$ 1 ≦ v_i ≦ 10^7 $

$ W, w_i, v_i $ はすべて整数である

Sample Explanation 1

$ 1, 3 $ 個目の物を選ぶと良いです。

Sample Explanation 2

$ 2, 4 $ 個目の物を選ぶと良いです。

Sample Explanation 3

すべての物が選べます。

Sample Explanation 4

$ 1 $ 個も物が選べません。

思路

一开始，一眼01背包，交上去RE了qwq。

仔细一看，才发现范围竟然是$10^9$,然后自己又眼瞎，没看到$w_1\leq w_i \leq w_1+3$~~~~。

所以看题解喽。

前言

为什么我现在才发现这道题洛谷里面有……

题目链接

正解：01 背包

一道比较简单的创新 01 背包。

正解

如果按照背包的板子做，那么一定会 TLE 和 MLE。那如何优化呢？

我们注意到数据范围里有一句十分特殊的话：

对于每个$i=2,3,···n$，满足$W_1\leq W_i\leq W_1+3$

那么我们完全可以把每个物品的重量以$W_1$为基准，转化为一个不超过3的数。这么可以极大地优化空间复杂度。

用$h$代表$W_1$的真实数字。

但是这样的话，我们就无法得知我们现在装的东西到底有没有超过背包的容量，因为我们并不知道我们选了多少个东西。所以$dp$数组还需要开一维代表选择物品的个数。

所以$dp_{i,j,k}$代表在前$i$个物品中选择$k$个物品，背包容量为$j$时的最大价值。

还需要注意一下循环的范围：

$i：1-n$

（这个不需要解释了吧……）

$j:0-3*i$

（因为物品的重量被处理过，当原来的$W_i=W_1$时这个物品的重量为0。所以最小的背包容量有可能是 00。物品最大的重量不超过3，有$i$个物品，所以最大可能容量为$3*i$。）

$k:1-i$

（选择的物品数量不能超过总数。因为后面求答案$ans$的初始值就为0已经包括了一个都不选的情况，所以不需要考虑不选物品的情况。）

最后求答案的时候需要枚举$dp_{n,i,j}$，注意只有$i+j*h\leq m$时背包才不超限，可以更新答案。

具体见代码。

Code
#include<cstdio>
#define max(a,b) (a)>(b)?(a):(b) //卡常小技巧：用这个比库函数要快一些
#define ll long long
ll n,m,ans,h,w[105],v[105],dp[105][305][105];
int main(){
	scanf("%lld %lld",&n,&m);
	scanf("%lld %lld",&h,&v[1]); //h 代表 W1 的的重量
	for(int i=2;i<=n;i++){
		scanf("%lld %lld",&w[i],&v[i]);
		w[i]-=h; //以 W1 为基准转化每一件物品的重量
	}
	for(int i=1;i<=n;i++){
		for(int k=1;k<=i;k++){ //选择的物品数量不能大于总数量
			for(int j=0;j<=3*i;j++){ //3*i 为被允许的最大容量
				if(j<w[i])
					dp[i][j][k]=dp[i-1][j][k];
				else
					dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-1]+v[i]);
			}
		}
	}
    //在合法的范围内寻找最大值
	for(int i=0;i<=3*n;i++){
		for(int j=0;j<=n;j++){
			if(i+j*h<=m)
				ans=max(ans,dp[n][i][j]);
		}
	}
	printf("%lld",ans);
	return 0;
}

再贴上另外一篇文章：题解AT_arc073_b - 洛谷专栏 (luogu.com.cn)