A. Road To Zero
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two integers x and y. You can perform two types of operations:
Pay a dollars and increase or decrease any of these integers by 1. For example, if x=0 and y=7 there are four possible outcomes after this operation:
x=0, y=6;
x=0, y=8;
x=−1, y=7;
x=1, y=7.
Pay b dollars and increase or decrease both integers by 1. For example, if x=0 and y=7 there are two possible outcomes after this operation:
x=−1, y=6;
x=1, y=8.
Your goal is to make both given integers equal zero simultaneously, i.e. x=y=0. There are no other requirements. In particular, it is possible to move from x=1, y=0 to x=y=0.
Calculate the minimum amount of dollars you have to spend on it.
Input
The first line contains one integer t (1≤t≤100) — the number of testcases.
The first line of each test case contains two integers x and y (0≤x,y≤109).
The second line of each test case contains two integers a and b (1≤a,b≤109).
Output
For each test case print one integer — the minimum amount of dollars you have to spend.
Example
inputCopy
2
1 3
391 555
0 0
9 4
outputCopy
1337
0
Note
In the first test case you can perform the following sequence of operations: first, second, first. This way you spend 391+555+391=1337 dollars.
In the second test case both integers are equal to zero initially, so you dont’ have to spend money.
题意:
题意不算难懂,简单说下:
1.花费a元:对x,y其中
任意一个
增大或减小1
2.花费b元:对x,y
同时
增加或者减小1,即同增同减
求最少花多少元能让x,y都变成0
思路:
思路是找出两个数的差,这部分通过第一步来操作,剩下的部分由b来操作
但是具体要分两种情况
- x,y同号:
- x,y异号:
具体操作看代码,比较简单,不多说了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
int main()
{
int t;
ll x, y;
ll a, b;
cin >> t;
while (t--)
{
cin >> x >> y;
cin >> a >> b;
if (x == 0 && y == 0)
{
cout << '0' << endl;
continue;
}
else
{
ll m = max(x, y);
ll n = min(x, y);
ll u = m - n;
ll ans;
if (x * y >= 0)
ans = min((x + y) * a, n * b + u * a);
else
ans = min(n * b + (m + n) * a, u * a);
cout << ans << endl;
}
}
return 0;
}
B. Binary Period
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let’s say string s has period k if si=si+k for all i from 1 to |s|−k (|s| means length of string s) and k is the minimum positive integer with this property.
Some examples of a period: for s=“0101” the period is k=2, for s=“0000” the period is k=1, for s=“010” the period is k=2, for s=“0011” the period is k=4.
You are given string t consisting only of 0’s and 1’s and you need to find such string s that:
String s consists only of 0’s and 1’s;
The length of s doesn’t exceed 2⋅|t|;
String t is a subsequence of string s;
String s has smallest possible period among all strings that meet conditions 1—3.
Let us recall that t is a subsequence of s if t can be derived from s by deleting zero or more elements (any) without changing the order of the remaining elements. For example, t=“011” is a subsequence of s=“10101”.
Input
The first line contains single integer T (1≤T≤100) — the number of test cases.
Next T lines contain test cases — one per line. Each line contains string t (1≤|t|≤100) consisting only of 0’s and 1’s.
Output
Print one string for each test case — string s you needed to find. If there are multiple solutions print any one of them.
Example
inputCopy
4
00
01
111
110
outputCopy
00
01
11111
1010
Note
In the first and second test cases, s=t since it’s already one of the optimal solutions. Answers have periods equal to 1 and 2, respectively.
In the third test case, there are shorter optimal solutions, but it’s okay since we don’t need to minimize the string s. String s has period equal to 1.
题意
就是给你一个字符串t(只包含0和1),让你求周期最小的字符串s,并输出。
s满足的条件:
- 字符串s只包含0和1;
- s的长度不超过2⋅t ;(t是字符串t的长度)
- 字符串t是字符串s的子序列;
在满足条件1-3的所有字符串中,字符串s的周期可能最小。
思路:
题目中已经给了足够的提示,就是通过字符的增添和删减来构造新的字符串
-
很显然如果字符串t全由1或者0构成,此时周期就为
1
,不需要构建新的,直接输出t就可 -
但是既有1又有0时,容易想到最小周期是
2
,这就需要构造01010101…
或者10101010…这两种序列
具体实现请看代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
int main()
{
int T;
char t[101], s[202];
cin >> T;
while (T--)
{
cin >> t;
int flag = 0;
int len = strlen(t);
int sum = 0;
for (int i = 0; i < len; i++)
sum += (t[i]-'0');
if ((sum == 0) || (sum == len))
{
cout << t << endl;
continue;
}
else
{
for (int i = 0; i < len-1; i++)
{
if (t[i] == t[i + 1] && t[i] == '0')
{
cout << t[i] << '1'; continue;
}
else if (t[i] == t[i + 1] && t[i] == '1')
{
cout << t[i] << '0'; continue;
}
else
{
cout << t[i]; continue;
}
}
cout << t[len - 1] << endl;
}
}
return 0;
}
比赛时就做出了AB两道题,c题的题意完全不懂,比赛结束后才弄懂的
C. Yet Another Counting Problem
time limit per test3.5 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two integers a and b, and q queries. The i-th query consists of two numbers li and ri, and the answer to it is the number of integers x such that li≤x≤ri, and ((xmoda)modb)≠((xmodb)moda). Calculate the answer for each query.
Recall that ymodz is the remainder of the division of y by z. For example, 5mod3=2, 7mod8=7, 9mod4=1, 9mod9=0.
Input
The first line contains one integer t (1≤t≤100) — the number of test cases. Then the test cases follow.
The first line of each test case contains three integers a, b and q (1≤a,b≤200; 1≤q≤500).
Then q lines follow, each containing two integers li and ri (1≤li≤ri≤1018) for the corresponding query.
Output
For each test case, print q integers — the answers to the queries of this test case in the order they appear.
Example
inputCopy
2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200
outputCopy
0 0 0 2 4
0 91
题意:
[l,r][l,r][l,r]范围内多少个数满足 (x % b) % a != (x % a) % b。
思路:
打表找规律。
假设b>ab > ab>a
可以发现当为 lcm(a,b)倍数的时候,再连续b个数字,是那个式子满足相等的。
找出多少个相等的,就可以知道不相等的个数了。
明显对于k∗lcm(a,b)的数,%b或者%a都为0。那么肯定相等。连续b个数字下,模b不变,只用看模a,所以肯定相等。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, q;
ll Lcm;
ll gcd(ll n, ll m) {
return m == 0 ? n : gcd(m, n % m);
}
ll lcm(ll n, ll m) {
return n / gcd(n, m) * m;
}
ll cal(ll x) {
ll res = 0;
ll num = x / Lcm;
res += num * b;
if (num != 0) {
x %= num * Lcm;
}
x += 1;
res += min(x, b);
return res;
}
int main() {
int t;
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld%lld", &a, &b, &q);
if (a > b) swap(a, b);
Lcm = lcm(a, b);
while (q--) {
ll l, r; scanf("%lld%lld", &l, &r);
ll ans = cal(r) - cal(l - 1);
ans = r - l + 1 - ans;
printf("%lld ", ans);
}
printf("\n");
}
return 0;
}
本人水平有限,如有错误,请指正