B. String LCM
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let’s define a multiplication operation between a string a and a positive integer x: a⋅x is the string that is a result of writing x copies of a one after another. For example, “abc” ⋅ 2 = “abcabc”, “a” ⋅ 5 = “aaaaa”.
A string a is divisible by another string b if there exists an integer x such that b⋅x=a. For example, “abababab” is divisible by “ab”, but is not divisible by “ababab” or “aa”.
LCM of two strings s and t (defined as LCM(s,t)) is the shortest non-empty string that is divisible by both s and t.
You are given two strings s and t. Find LCM(s,t) or report that it does not exist. It can be shown that if LCM(s,t) exists, it is unique.
Input
The first line contains one integer q (1≤q≤2000) — the number of test cases.
Each test case consists of two lines, containing strings s and t (1≤|s|,|t|≤20). Each character in each of these strings is either ‘a’ or ‘b’.
Output
For each test case, print LCM(s,t) if it exists; otherwise, print -1. It can be shown that if LCM(s,t) exists, it is unique.
Example
inputCopy
3
baba
ba
aa
aaa
aba
ab
outputCopy
baba
aaaaaa
-1
Note
In the first test case, “baba” = “baba” ⋅ 1 = “ba” ⋅ 2.
In the second test case, “aaaaaa” = “aa” ⋅ 3 = “aaa” ⋅ 2.
找到他們的最小公倍數然後看他們分别構成的那個字元串是否相等
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define Ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
const int mod = 1e9 + 7;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 11000;
const int M = 1e6 + 10;
signed main(){
// freopen("C:\\Users\\wwb0719\\Desktop\\stdin.txt", "r", stdin);
// Ios
int T;
gt(T);
while(T --){
string str1, str2;
cin >> str1 >> str2;
int mind = min(str1.size(), str2.size());
int cnt = 1;
for (int i = 1; ; i ++){
if (i * mind % str1.size() == 0 && i * mind % str2.size() == 0){
cnt = i;
break;
}
}
string str3;
for (int i = 1; i <= cnt; i ++){
if (str1.size() < str2.size()) str3 += str1;
else str3 += str2;
}
string str4, str5;
for (int i = 1; i <= (str3.size() / str1.size()); i ++){
str4 += str1;
}
for (int i = 1; i <= (str3.size() / str2.size()); i ++){
str5 += str2;
}
if (str4 != str5) cout << "-1" << endl;
else cout << str3 << endl;
}
return 0;
}
C. No More Inversions
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You have a sequence a with n elements 1,2,3,…,k−1,k,k−1,k−2,…,k−(n−k) (k≤n<2k).
Let’s call as inversion in a a pair of indices i<j such that a[i]>a[j].
Suppose, you have some permutation p of size k and you build a sequence b of size n in the following manner: b[i]=p[a[i]].
Your goal is to find such permutation p that the total number of inversions in b doesn’t exceed the total number of inversions in a, and b is lexicographically maximum.
Small reminder: the sequence of k integers is called a permutation if it contains all integers from 1 to k exactly once.
Another small reminder: a sequence s is lexicographically smaller than another sequence t, if either s is a prefix of t, or for the first i such that si≠ti, si<ti holds (in the first position that these sequences are different, s has smaller number than t).
Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.
The first and only line of each test case contains two integers n and k (k≤n<2k; 1≤k≤105) — the length of the sequence a and its maximum.
It’s guaranteed that the total sum of k over test cases doesn’t exceed 105.
Output
For each test case, print k integers — the permutation p which maximizes b lexicographically without increasing the total number of inversions.
It can be proven that p exists and is unique.
Example
inputCopy
4
1 1
2 2
3 2
4 3
outputCopy
1
1 2
2 1
1 3 2
Note
In the first test case, the sequence a=[1], there is only one permutation p=[1].
In the second test case, the sequence a=[1,2]. There is no inversion in a, so there is only one permutation p=[1,2] which doesn’t increase the number of inversions.
In the third test case, a=[1,2,1] and has 1 inversion. If we use p=[2,1], then b=[p[a[1]],p[a[2]],p[a[3]]]=[2,1,2] and also has 1 inversion.
In the fourth test case, a=[1,2,3,2], and since p=[1,3,2] then b=[1,3,2,3]. Both a and b have 1 inversion and b is the lexicographically maximum.
a數組中的逆序對就是 k ,之後的數。如[1,2,3,4,3,2]，就是[4,3,2]，這一部分。生成的b數組的後半部分（左右對稱的部分）就是[p[2],p[3],p[4],p[3],p[2]]，可以發現，如果p數組就是有序的，那麼生成的就是 23432，逆序對數量一定是等于a數組的，因為其實就是b數組等于a數組了，一模一樣，但是，如果p中這部分值是逆序的，那麼生成的就是 43234，逆序對數量也等于a數組！！。那麼顯然逆序排列是字典序最大的。是以答案就是這個東西了！前面不對稱的部分不能改，改了逆序對就比a數組更多。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int mod = 1e9 + 7;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 11000;
const int M = 1e6 + 10;
signed main(){
// freopen("C:\\Users\\wwb0719\\Desktop\\stdin.txt", "r", stdin);
ios;
int T;
gt(T);
while(T --){
int n, k;
gt(n), gt(k);
int res = (n - k);
int temp = (k - res - 1);
for (int i = 1; i <= temp; i ++) cout << i << " ";
for (int i = k; i > temp; i --) cout << i << " ";
cout << endl;
}
return 0;
}
D. Program
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a program that consists of n instructions. Initially a single variable x is assigned to 0. Afterwards, the instructions are of two types:
increase x by 1;
decrease x by 1.
You are given m queries of the following format:
query l r — how many distinct values is x assigned to if all the instructions between the l-th one and the r-th one inclusive are ignored and the rest are executed without changing the order?
Input
The first line contains a single integer t (1≤t≤1000) — the number of testcases.
Then the description of t testcases follows.
The first line of each testcase contains two integers n and m (1≤n,m≤2⋅105) — the number of instructions in the program and the number of queries.
The second line of each testcase contains a program — a string of n characters: each character is either ‘+’ or ‘-’ — increment and decrement instruction, respectively.
Each of the next m lines contains two integers l and r (1≤l≤r≤n) — the description of the query.
The sum of n over all testcases doesn’t exceed 2⋅105. The sum of m over all testcases doesn’t exceed 2⋅105.
Output
For each testcase print m integers — for each query l, r print the number of distinct values variable x is assigned to if all the instructions between the l-th one and the r-th one inclusive are ignored and the rest are executed without changing the order.
Example
inputCopy
2
8 4
-±-±-+
1 8
2 8
2 5
1 1
4 10
±++
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4
outputCopy
1
2
4
4
3
3
4
2
3
2
1
2
2
2
Note
The instructions that remain for each query of the first testcase are:
empty program — x was only equal to 0;
“-” — x had values 0 and −1;
“—+” — x had values 0, −1, −2, −3, −2 — there are 4 distinct values among them;
“±-±-+” — the distinct values are 1, 0, −1, −2.
處理一個前面符号處理後的可以得到的最大的數和最小的數分别是多少，在處理出每個數的時候是多少，再向後處理出每個位置向後走最大能加多少，最小能加多少，查詢的時候就可以知道這一段數在加減的過程中最大的數和最小的數分别是多少了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int mod = 1e9 + 7;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 2e5 + 10;
const int M = 1e6 + 10;
int h[N], a[N], b[N], c[N], d[N];
//倒序循環，倒序字尾和
//對字元串有處理下标從1開始，讀入char
signed main(){
// freopen("C:\\Users\\wwb0719\\Desktop\\stdin.txt", "r", stdin);
ios;
int T;
scanf("%lld",&T);
while(T--){
int n, m;
char s[N];
scanf("%lld%lld",&n,&m);
scanf("%s",s+1);
for(int i=1; i<=n; i++){
if(s[i]=='+')
h[i]=h[i-1]+1;
else
h[i]=h[i-1]-1;
a[i]=max(a[i-1],h[i]);
b[i]=min(b[i-1],h[i]);
}
c[n+1]=0,d[n+1]=0;
for(int i=n; i>=1; i--){
int v=s[i]=='+'?1:-1;
c[i]=max(0ll,c[i+1]+v);
d[i]=min(0ll,d[i+1]+v);
}
for(int i=1; i<=m; i++){
int l,r,A,B;
scanf("%d%d",&l,&r);
A=max(a[l-1],h[l-1]+c[r+1]);
B=min(b[l-1],h[l-1]+d[r+1]);
printf("%lld\n",A-B+1);
}
}
return 0;
}
![POJ 2352 Stars 【線段樹】[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)