A. Vertices in the Pocket
Time Limit: 2 Seconds Memory Limit: 65536 KB
DreamGrid has just found an undirected simple graph with n vertices and no edges (that's to say, it's a graph with n isolated vertices) in his right pocket, where the vertices are numbered from 1 to n. Now he would like to perform q operations of the following two types on the graph:
- 1 a b -- Connect the a-th vertex and the b-th vertex by an edge. It's guaranteed that before this operation, there does not exist an edge which connects vertex aand b directly.
- 2 k -- Find the answer for the query: What's the minimum and maximum possible number of connected components after adding k new edges to the graph. Note that after adding the k edges, the graph must still be a simple graph, and the query does NOT modify the graph.
Please help DreamGrid find the answer for each operation of the second type. Recall that a simple graph is a graph with no self loops or multiple edges.
Input
There are multiple test cases. The first line of the input is an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and q (1≤n≤105, 1≤q≤2×105), indicating the number of vertices and the number of operations.
For the following q lines, the i-th line first contains an integer pi (pi∈{1,2}), indicating the type of the i-th operation.
- If pi=1, two integers ai and bi follow (1≤ai,bi≤n, ai≠bi), indicating an operation of the first type. It's guaranteed that before this operation, there does not exist an edge which connects vertex a and b directly.
- If pi=2, one integer ki follows (0≤ki≤n(n−1)2), indicating an operation of the second type. It's guaranteed that after adding ki edges to the graph, the graph is still possible to be a simple graph.
It's guaranteed that the sum of n in all test cases will not exceed 106, and the sum of q in all test cases will not exceed 2e6
Output
For each operation of the second type output one line containing two integers separated by a space, indicating the minimum and maximum possible number of connected components in this query.
Sample Input
1
5 5
1 1 2
2 1
1 1 3
2 1
2 3
Sample Output
3 3
2 3
1 2
待补
B. Element Swapping
Time Limit: 1 Second Memory Limit: 65536 KB
DreamGrid has an integer sequence a1,a2,…,an and he likes it very much. Unfortunately, his naughty roommate BaoBao swapped two elements ai and aj (1≤i<j≤n) in the sequence when DreamGrid wasn't at home. When DreamGrid comes back, he finds with dismay that his precious sequence has been changed into a1,a2,…ai−1,aj,ai+1,…,aj−1,ai,aj+1,…,an!
What's worse is that DreamGrid cannot remember his precious sequence. What he only remembers are the two valuesx=n∑k=1kakandy=n∑k=1ka2kGiven the sequence after swapping and the two values DreamGrid remembers, please help DreamGrid count the number of possible element pairs (ai,aj) BaoBao swaps.
Note that as DreamGrid is poor at memorizing numbers, the value of x or y might not match the sequence, and no possible element pair can be found in this situation.
Two element pairs (ai,aj) (1≤i<j≤n) and (ap,aq) (1≤p<q≤n) are considered different if i≠p or j≠q.
Input
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains three integers n, x and y (2≤n≤105,1≤x,y≤1018), indicating the length of the sequence and the two values DreamGrid remembers.
The second line contains n integers b1,b2,…,bn (1≤bi≤105), indicating the sequence after swapping. It's guaranteed that n∑k=1kbk≤1018 and n∑k=1kb2k≤1018.
It's guaranteed that the sum of n of all test cases will not exceed 2×106.
Output
For each test case output one line containing one integer, indicating the number of possible element pairs BaoBao swaps.
Sample Input
2
6 61 237
1 1 4 5 1 4
3 20190429 92409102
1 2 3
Sample Output
2
0
Hint
For the first sample test case, it’s possible that BaoBao swaps the 2nd and the 3rd element, or the 5th and the 6th element.
数学题，由于只交换了两个元素，那么我们考虑这两个位置的交换对 x 和 y 的影响；
因此 \(x_2−x_1=(i−j)\times (a_i−a_j) \)，同理\(y_2-y_1=(i-j)\times ({a_i}^2-{a_j}^2)\)
即\(y_2−y_1=(i−j)\times (a_i−a_j)\times (a_i+a_j)\)
于是\(\frac{y}{x}=a_i+a_j\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
ll b[maxn],num[maxn];
set<ll> s;
int main(){
int t;cin>>t;
while(t--){
int n;ll x,y;scanf("%d%lld%lld",&n,&x,&y);
ll xx=0,yy=0;ll num[maxn]={0,};s.clear();
rep(i,1,n){
scanf("%lld",&b[i]);xx+=(ll)i*b[i];yy+=(ll)i*b[i]*b[i];
s.insert(b[i]);num[b[i]]++;
}
yy-=y;xx-=x; ll ans=0;
if(xx==0&&yy==0){
for(auto it=s.begin();it!=s.end();++it)
if(num[*it]>1) ans+=(num[*it]*(num[*it]-1))/2ll;
}
else if(yy!=0&&xx!=0){
if(yy%xx==0){
ll tem=yy/xx;
for(ll i=1;i<=n;++i){
ll op=tem-b[i];
if(op>0&&op<=(1e5)&&num[op]){
ll v=2*b[i]-tem;
if(v&&xx%v==0){
int jj=i-xx/v;
if(jj<=n&&jj>i&&b[jj]==op) ans++;
}
}
}
}
}
printf("%lld\n",ans);
}
}
C. Array in the Pocket
Time Limit: 2 Seconds Memory Limit: 65536 KB
BaoBao has just found an array A={a1,a2,…,an} of n integers in his left pocket. As BaoBao is bored, he decides to rearrange it into another array B={b1,b2,…,bn} of n integers such that B is a permutation of A, and ai≠bi for all 1≤i≤n. Please help BaoBao finish the rearragement.
If multiple valid rearrangements exist, find the smallest one among them.
Consider two arrays C={c1,c2,…,cn} and D={d1,d2,…,dn}, we say C is smaller than D if there exists an integer k such that 1≤k≤n, ci=di for all 1≤i<k, and ck<dk.
Input
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105), indicating the length of the array.
The second line contains n integers a1,a2,…,an (1≤ai≤n), indicating the given array.
Output
For each test case output one line containing n integers b1,b2,…,bn separated by a space, indicating the answer. If there are multiple valid answers, output the smallest one. If no valid answer exists, print "Impossible" (without quotes) instead.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
Sample Input
3
4
4 1 3 2
4
1 1 2 3
3
1 1 1
Sample Output
1 2 4 3
2 3 1 1
Impossible
首先任意想到，如果一个数出现的次数大于n/2就是不可能的
用set维护两个二元组，其中s2存的是数字x和x的数量cnt[x]
s1存的是x在此位置之后还需要填的个数+x不能填的位置的个数
从前往后做，如果当前这个位置出现了la[x]==n-i+1（n-i+1即为当前这个位置之后序列的长度），则这个位置必定只能填x，否则之后就会无解（因为之后n-i+1就会减小1，但是还需要填的x的数量没变，肯定填不完），然后如果没有必须要填的数的话就填当前字典序最小的并且和a[i]不一样的数
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 0x7fffffff
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define F first
#define S second
const int maxn=(int)1e5+100;
int a[maxn],ans[maxn],cnt[maxn],la[maxn];
typedef pair<int,int> p;
set<p> s1,s2;
int main(){
int T;cin>>T;
while(T--){
int a[maxn],n,flag=0;;cin>>n; s1.clear(); s2.clear();
rep(i,0,n) cnt[i]=0,la[i]=0;
rep(i,1,n){
scanf("%d",&a[i]);cnt[a[i]]++;la[a[i]]+=2;
if(cnt[a[i]]>n/2) flag=1;
} if(flag) {puts("Impossible");continue;}
rep(i,1,n)
if(cnt[i]) s1.insert(p(la[i],i)),s2.insert(p(i,cnt[i]));
rep(i,1,n){
s1.erase(p(la[a[i]],a[i])); s1.insert(p(--la[a[i]],a[i]));
p mx=*(--s1.end());
if(mx.F==n-i+1) ans[i]=mx.S;
else ans[i]=a[i]==(s2.begin())->F?((++s2.begin())->F):(s2.begin())->F;
s1.erase(p(la[ans[i]],ans[i]));
if(--la[ans[i]]) s1.insert(p(la[ans[i]],ans[i]));
s2.erase(p(ans[i],cnt[ans[i]]));
if(--cnt[ans[i]]) s2.insert(p(ans[i],cnt[ans[i]]));
}
rep(i,1,n) printf(i==1?"%d":" %d",ans[i]); puts("");
}
}
D. Traveler
Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge
The famous traveler BaoBao is visiting the Dream Kingdom now. There are n cities in Dream Kingdom, numbered from 1 to n. The cities are connected by directedroads. For all 1≤i≤n:
- There is a road from the i-th city to the (i−1)-th city if 1≤i−1≤n.
- There is a road from the i-th city to the 2i-th city if 1≤2i≤n.
- There is a road from the i-th city to the (2i+1)-th city if 1≤2i+1≤n.
- There is a road from the i-th city to the ⌊i2⌋-th city if 1≤⌊i2⌋≤n, where ⌊i2⌋ indicates the largest integer x such that 2x≤i.
BaoBao starts his travel from the 1st city. As he doesn't like visiting a city more than once, he wants to find a route which goes through each of the n cities exactly once. Can you help him find such a route?
Input
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first and the only line contains an integer n (1≤n≤105), indicating the number of cities in Dream Kingdom.
It's guaranteed that the sum of n of all test cases will not exceed 106.
Output
For each test case output one line. If there exists a route which starts from the 1st city and visits each city exactly once, output n integers c1,c2,…,cn separated by a space, where ci indicates the i-th city in the route (note that according to the description, there must be c1=1). If there is no valid route, output "-1" (without quotes) instead. If there are multiple valid answers, you can output any of them.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
Sample Input
2
2
9
Sample Output
1 2
1 3 6 5 2 4 9 8 7
待补
E. Sequence in the Pocket
Time Limit: 2 Seconds Memory Limit: 65536 KB
DreamGrid has just found an integer sequence a1,a2,…,an in his right pocket. As DreamGrid is bored, he decides to play with the sequence. He can perform the following operation any number of times (including zero time): select an element and move it to the beginning of the sequence.
What's the minimum number of operations needed to make the sequence non-decreasing?
Input
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105), indicating the length of the sequence.
The second line contains n integers a1,a2,…,an (1≤ai≤109), indicating the given sequence.
It's guaranteed that the sum of n of all test cases will not exceed 106.
Output
For each test case output one line containing one integer, indicating the answer.
Sample Input
2
4
1 3 2 4
5
2 3 3 5 5
Sample Output
2
0
Hint
For the first sample test case, move the 3rd element to the front (so the sequence become {2, 1, 3, 4}), then move the 2nd element to the front (so the sequence become {1, 2, 3, 4}). Now the sequence is non-decreasing.
For the second sample test case, as the sequence is already sorted, no operation is needed.
先构造一个排好序的数组b然后从a的最后一个元素向前和b对比，如果一样的话那这个数就不用操作，把b的pos向前移动一位，如果不相等的话肯定是a<b的，那么在找到相等元素之前我们肯定有策略可以将这段比b[pos]小的数排成有序，重复这个过程知道a比完，此时我们已经知道了有几个数不用操作，那么答案自然就是n-cnt；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
int a[maxn],b[maxn];
rep(i,1,n) scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);int cnt=0,pos=n;
dep(i,n,1){
if(a[i]==b[pos]){cnt++;pos--;}
}
printf("%d\n",n-cnt);
}
}
F. Abbreviation
Time Limit: 1 Second Memory Limit: 65536 KB
In the Test of English as a Foreign Language (TOEFL), the listening part is very important but also very hard for most students since it is usually quite hard for them to remember the whole passage. To help themselves memorize the content, students can write down some necessary details. However, it is not easy to write down the complete word because of its length. That's why we decide to use the abbreviation to express the whole word.
It is very easy to get the abbreviation, all we have to do is to keep the consonant letters and erase the vowel. In the English alphabet, we regard 'a', 'e', 'i', 'y', 'o', 'u' as the vowels and the other letters as the consonants. For example, "subconscious" will be expressed as "sbcnscs".
However, there is one exception: if the vowel appears as the first letter, they should be kept instead of thrown away. For example, "oipotato" should be expressed as "optt".
Since you have learned how to use the abbreviation method, it's time for some exercises. We now present you T words in total, it's your task to express them in their abbreviation form.
Input
There are multiple test cases. The first line of the input contains an integer T (about 100), indicating the number of test cases. For each test case:
The only line contains a string s (1≤|s|≤100) consisting of lowercase English letters, indicating the word which needs to be abbreviated.
Output
For each test case output one line containing one string, which is the correct abbreviation of the given word.
Sample Input
5
subconscious
oipotato
word
symbol
apple
Sample Output
sbcnscs
optt
wrd
smbl
appl
签到题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int main(){
int t;cin>>t;
while(t--){
string s;cin>>s;cout<<s[0];
rep(i,1,s.length()-1)
if(s[i]!='a'&&s[i]!='e'&&s[i]!='i'&&s[i]!='o'&&s[i]!='y'&&s[i]!='u')
cout<<s[i];
cout<<endl;
}
}
G. Lucky 7 in the Pocket
Time Limit: 1 Second Memory Limit: 65536 KB
BaoBao loves number 7 but hates number 4, so he refers to an integer x as a "lucky integer" if x is divisible by 7 but not divisible by 4. For example, 7, 14 and 21 are lucky integers, but 1, 4 and 28 are not.
Today BaoBao has just found an integer n in his left pocket. As BaoBao dislikes large integers, he decides to find a lucky integer m such that m≥n and m is as small as possible. Please help BaoBao calculate the value of m.
Input
There are multiple test cases. The first line of the input is an integer T (about 100), indicating the number of test cases. For each test case:
The first and only line contains an integer n (1≤n≤100), indicating the integer in BaoBao's left pocket.
Output
For each test case output one line containing one integer, indicating the value of m.
Sample Input
4
1
7
20
28
Sample Output
7
7
21
35
n<100，暴力莽
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
for(int i=0;i<=200;i+=7){
if(i>=n&&i%4){cout<<i<<endl;break;}
}
}
}
H. Singing Everywhere
Time Limit: 2 Seconds Memory Limit: 65536 KB
Baobao loves singing very much and he really enjoys a game called Singing Everywhere, which allows players to sing and scores the players according to their performance.
Consider the song performed by Baobao as an integer sequence a1,a2,…,an, where ai indicates the i-th note in the song. We say a note ak is a "voice crack" if 1<k<n, ak−1<ak and ak+1<ak. The more voice cracks BaoBao sings, the lower score he gets.
To get a higher score, BaoBao decides to delete at most one note in the song. What's the minimum number of times BaoBao sings a voice crack after this operation?
Input
There are multiple test cases. The first line of the input contains an integer T (about 100), indicating the number of test cases. For each test case:
The first line contains one integer n (1≤n≤105), indicating the length of the song.
The second line contains n integers a1,a2,…,an (−231≤ai<231), indicating the song performed by BaoBao.
It's guaranteed that at most 5 test cases have n>100.
Output
For each test case output one line containing one integer, indicating the answer.
Sample Input
3
6
1 1 4 5 1 4
7
1 9 1 9 8 1 0
10
2 1 4 7 4 8 3 6 4 7
Sample Output
1
0
2
Hint
For the first sample test case, BaoBao does not need to delete a note. Because if he deletes no note, he will sing 1 voice crack (the 4th note), and no matter which note he deletes, he will also always sing 1 voice crack.
For the second sample test case, BaoBao can delete the 3rd note, and no voice cracks will be performed. Yay!
For the third sample test case, BaoBao can delete the 4th note, so that only 2 voice cracks will be performed (4 8 3 and 3 6 4).
很明显去掉一个点之后波峰的数量只有可能减少0，1，2三种可能，暴力枚举每个点然后更新答案就好了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 0x7fffffff
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int a[maxn];
int ck(int x){return a[x]>a[x-1]&&a[x]>a[x+1];}
int f1(int x){return a[x]>a[x-1]&&a[x]>a[x+2];}
int f2(int x){return a[x]>a[x+1]&&a[x]>a[x-2];}
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
int tot=0,flag=0;a[0]=a[n+1]=INF;
rep(i,1,n) scanf("%d",&a[i]);
rep(i,2,n-1){
if(ck(i)) tot++;
int tem=0;
if(f1(i-1)==0&&ck(i-1)) tem++;
if(f2(i+1)==0&&ck(i+1)) tem++;
flag=max(flag,tem);
}
printf("%d\n",tot-flag);
}
}
I. Fibonacci in the Pocket
Time Limit: 1 Second Memory Limit: 65536 KB
DreamGrid has just found a Fibonacci sequence f1,f2,… and two integers a and b in his right pocket, where fk indicates the k-th element in the Fibonacci sequence.
Please tell DreamGrid if b∑i=afi is even or is odd.
Recall that a Fibonacci sequence is an infinite sequence which satisfies f1=1, f2=1 and fi=fi−1+fi−2 for all i≥3.
Input
There are multiple test cases. The first line of the input contains an integer T (about 100), indicating the number of test cases. For each test case:
The first and only line contains two integers a and b (1≤a≤b<1010000). Their meanings are described above.
Output
For each test case output one line. If b∑i=afi is even output "0" (without quotes); If b∑i=afi is odd output "1" (without quotes).
Sample Input
6
1 2
1 3
1 4
1 5
123456 12345678987654321
123 20190427201904272019042720190427
Sample Output
0
0
1
0
0
1
Hint
The first few elements of the Fibonacci sequence are: f1=1, f2=1, f3=2, f4=3, f5=5, f6=8...
算是一道水题，需要注意的是a和b的范围不能用普通方法做，但是考虑到mod的是3，因此可以将每一位数加起来再mod 3
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 0x7fffffff
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int main(){
int t;cin>>t;
while(t--){
string a,b;cin>>a>>b;
ll aa=0,bb=0;
rep(i,0,a.length()-1) aa+=a[i]-'0'; aa%=3;
rep(i,0,b.length()-1) bb+=b[i]-'0'; bb%=3;
if(aa==0) aa=3;if(bb==0) bb=3;aa--;
int flag=0;
if(bb==1) flag=1;
if(aa==1) {flag^=1;}
if(flag) puts("1");
else puts("0");
}
}
J. Welcome Party
Time Limit: 2 Seconds Memory Limit: 131072 KB
The 44th World Finals of the International Collegiate Programming Contest (ICPC 2020) will be held in Moscow, Russia. To celebrate this annual event for the best competitive programmers around the world, it is decided to host a welcome party for all n participants of the World Finals, numbered from 1 to n for convenience.
The party will be held in a large hall. For security reasons, all participants must present their badge to the staff and pass a security check in order to be admitted into the hall. Due to the lack of equipment to perform the security check, it is decided to open only one entrance to the hall, and therefore only one person can enter the hall at a time.
Some participants are friends with each other. There are m pairs of mutual friendship relations. Needless to say, parties are more fun with friends. When a participant enters the hall, if he or she finds that none of his or her friends is in the hall, then that participant will be unhappy, even if his or her friends will be in the hall later. So, one big problem for the organizer is the order according to which participants enter the hall, as this will determine the number of unhappy participants. You are asked to find an order that minimizes the number of unhappy participants. Because participants with smaller numbers are more important (for example the ICPC director may get the number 1), if there are multiple such orders, you need to find the lexicographically smallest one, so that important participants enter the hall first.
Please note that if participant a and b are friends, and if participant b and c are friends, it's NOT necessary that participant a and c are friends.
Input
There are multiple test cases. The first line of the input contains a positive integer T, indicating the number of cases. For each test case:
The first line contains two integers n and m (1≤n,m≤106), the number of participants and the number of friendship relations.
The following m lines each contains two integers a and b (1≤a,b≤n,a≠b), indicating that the a-th and the b-th participant are friends. Each friendship pair is only described once in the input.
It is guaranteed that neither the sum of n nor the sum of m of all cases will exceed 106.
Output
For each case, print a single integer on the first line, indicating the minimum number of unhappy participants. On the second line, print a permutation of 1 to n separated by a space, indicating the lexicographically smallest ordering of participants entering the hall that achieves this minimum number.
Consider two orderings P=p1,p2,…,pn and Q=q1,q2,…,qn, we say P is lexicographically smaller than Q, if there exists an integer k (1≤k≤n), such that pi=qi holds for all 1≤i<k, and pk<qk.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
Sample Input
2
4 3
1 2
1 3
1 4
4 2
1 2
3 4
Sample Output
1
1 2 3 4
2
1 2 3 4
容易想到，不开心人的数量就是连通块的数量，至于选人策略跑一次优先队列的拓扑序就好了
坑点就是用邻接表存边会t，要用前向星
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int head[maxn],cnt;
int pre[maxn],vis[maxn];
priority_queue<int,vector<int>,greater<int> > q;
struct node{
int to,nex;
}g[maxn<<1];
void add(int u,int v){
g[cnt].to=v;
g[cnt].nex=head[u];
head[u]=cnt++;
}
int find(int x){
return x==pre[x]?x:pre[x]=find(pre[x]);
}
void join(int x,int y){
x=find(x);y=find(y);
x<y?pre[y]=x:pre[x]=y;
}
int main(){
int t;cin>>t;
while(t--){
int n,m;scanf("%d%d",&n,&m);
rep(i,1,n) head[i]=0,cnt=1,pre[i]=i,vis[i]=0;
while(m--){
int a,b;scanf("%d%d",&a,&b);
add(a,b);add(b,a);join(a,b);
}
int ans=0,fr=1;
rep(i,1,n) if(i==pre[i]) ans++,q.push(i),vis[i]=1;; printf("%d\n",ans);
while(!q.empty()){
int u=q.top(); q.pop(); printf(fr?"%d":" %d",u); fr=0;
for(int i=head[u];i!=0;i=g[i].nex){
if(vis[g[i].to]==0) q.push(g[i].to),vis[g[i].to]=1;
}
}
puts("");
}
}
Strings in the Pocket
Time Limit: 1 Second Memory Limit: 65536 KB
BaoBao has just found two strings s=s1s2…sn and t=t1t2…tn in his left pocket, where si indicates the i-th character in string s, and ti indicates the i-th character in string t.
As BaoBao is bored, he decides to select a substring of s and reverse it. Formally speaking, he can select two integers l and r such that 1≤l≤r≤n and change the string to s1s2…sl−1srsr−1…sl+1slsr+1…sn−1sn.
In how many ways can BaoBao change s to t using the above operation exactly once? Let (a,b) be an operation which reverses the substring sasa+1…sb, and (c,d) be an operation which reverses the substring scsc+1…sd. These two operations are considered different, if a≠c or b≠d.
Input
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains a string s (1≤|s|≤2×106), while the second line contains another string t (|t|=|s|). Both strings are composed of lower-cased English letters.
It's guaranteed that the sum of |s| of all test cases will not exceed 2×107.
Output
For each test case output one line containing one integer, indicating the answer.
Sample Input
2
abcbcdcbd abcdcbcbd
abc abc
Sample Output
3
3
Hint
For the first sample test case, BaoBao can do one of the following three operations: (2, 8), (3, 7) or (4, 6).
For the second sample test case, BaoBao can do one of the following three operations: (1, 1), (2, 2) or (3, 3).
傻逼题，因为这道题还被女朋友骂了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e6+100;
const int mod=(int)1e9+7;
char a[maxn],b[maxn];
int P[maxn<<1];
ll Manacher(string s){
string res="$#";
for(int i=0;i<s.size();++i){
res+=s[i]; res+="#";
}
ll ans=0;
int mi=0,right=0;
for(int i=1;i<res.size();++i){
P[i]=right>i ?min(P[2*mi-i],right-i):1;
while(res[i+P[i]]==res[i-P[i]])
++P[i];
if(right<i+P[i]){
right=i+P[i];
mi=i;
}
ans+=P[i]/2;
}
return ans;
}
int main(){
int t;cin>>t;
while(t--){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
scanf("%s%s",a,b);
int len=strlen(a);
int l=0,r=len-1;
while(l<len&&a[l]==b[l]) l++;
while(r>=0&&a[r]==b[r]) r--;
if(l>r) printf("%lld\n",Manacher(a));
else{
int flag=1;
if(l==r) {puts("0");continue;}
rep(i,l,r) if(a[i]!=b[l+r-i]) {flag=0;break;}
if(flag){
ll ans=1;l--;r++;
while(l>=0&&r<len&&a[l]==a[r]){ans++;l--;r++;}
printf("%d\n",ans);
}
else puts("0");
}
}
}
