本文共 6921 字,大约阅读时间需要 23 分钟。
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其中 任意一个 增大或减小12.花费b元:对x,y 同时 增加或者减小1,即同增同减
求最少花多少元能让x,y都变成0思路:
思路是找出两个数的差,这部分通过第一步来操作,剩下的部分由b来操作 但是具体要分两种情况具体操作看代码,比较简单,不多说了
#include#include #include #include #include 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;}
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满足的条件:在满足条件1-3的所有字符串中,字符串s的周期可能最小。
思路:
题目中已经给了足够的提示,就是通过字符的增添和删减来构造新的字符串很显然如果字符串t全由1或者0构成,此时周期就为1,不需要构建新的,直接输出t就可
但是既有1又有0时,容易想到最小周期是2,这就需要构造01010101…
或者10101010…这两种序列具体实现请看代码
#include#include #include #include #include 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题的题意完全不懂,比赛结束后才弄懂的
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#include #include 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;}
本人水平有限,如有错误,请指正
转载地址:http://rafdi.baihongyu.com/