A. Prime Subtraction
time limit per test2 seconds memory limit per test256 megabytes
You are given two integers x and y (it is guaranteed that \(x>y\)). You may choose any prime integer p and subtract it any number of times from x. Is it possible to make x equal to y?
Recall that a prime number is a positive integer that has exactly two positive divisors: 11 and this integer itself. The sequence of prime numbers starts with 2, 3, 5, 7, 11.
Your program should solve t independent test cases.
Input
The first line contains one integer t \((1 \le ? \le 1000)\) — the number of test cases.
Then ?t lines follow, each describing a test case. Each line contains two integers x and y \((1 \le ? < ? \le 10^{18})\).
Output
For each test case, print YES if it is possible to choose a prime number ?p and subtract it any number of times from ?x so that ?x becomes equal to ?y. Otherwise, print NO.
You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answer).
Exampleinput
4 100 98 42 32 1000000000000000000 1 41 40
output
YES YES YES N
Note
In the first test of the example you may choose p = 2 and subtract it once.
In the second test of the example you may choose p = 5 and subtract it twice. Note that you cannot choose p = 7, subtract it, then choose p = 3 and subtract it again.
In the third test of the example you may choose p = 3 and subtract it 333333333333333333 times.
签到
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
void solve(){
ll x,y;scanf("%lld%lld",&x,&y);
x-=y;
puts(x==1?"NO":"YES");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Kill 'Em All
time limit per test1 second memory limit per test256 megabytes
Ivan plays an old action game called Heretic. He's stuck on one of the final levels of this game, so he needs some help with killing the monsters.
The main part of the level is a large corridor (so large and narrow that it can be represented as an infinite coordinate line). The corridor is divided into two parts; let's assume that the point ?=0x=0 is where these parts meet.
The right part of the corridor is filled with ?n monsters — for each monster, its initial coordinate ??xi is given (and since all monsters are in the right part, every ??xi is positive).
The left part of the corridor is filled with crusher traps. If some monster enters the left part of the corridor or the origin (so, its current coordinate becomes less than or equal to 00), it gets instantly killed by a trap.
The main weapon Ivan uses to kill the monsters is the Phoenix Rod. It can launch a missile that explodes upon impact, obliterating every monster caught in the explosion and throwing all other monsters away from the epicenter. Formally, suppose that Ivan launches a missile so that it explodes in the point ?c. Then every monster is either killed by explosion or pushed away. Let some monster's current coordinate be ?y, then:
- if c=y, then the monster is killed;
- if y<c, then the monster is pushed ?r units to the left, so its current coordinate becomes y−r;
- if y>c, then the monster is pushed ?r units to the right, so its current coordinate becomes y+r.
Ivan is going to kill the monsters as follows: choose some integer point ?d and launch a missile into that point, then wait until it explodes and all the monsters which are pushed to the left part of the corridor are killed by crusher traps, then, if at least one monster is still alive, choose another integer point (probably the one that was already used) and launch a missile there, and so on.
What is the minimum number of missiles Ivan has to launch in order to kill all of the monsters? You may assume that every time Ivan fires the Phoenix Rod, he chooses the impact point optimally.
You have to answer q independent queries.
Input
The first line contains one integer q \((1 \le q \le 10^5)\) — the number of queries.
The first line of each query contains two integers n and r \((1 \le n, r \le 10^5)\) — the number of enemies and the distance that the enemies are thrown away from the epicenter of the explosion.
The second line of each query contains n integers \(x_i (1 \le x_i \le 10^5)\) — the initial positions of the monsters.
It is guaranteed that sum of all n over all queries does not exceed \(10^5\)
Output
For each query print one integer — the minimum number of shots from the Phoenix Rod required to kill all monsters.
Exampleinput
2 3 2 1 3 5 4 1 5 2 3 5
output
2
Note
In the first test case, Ivan acts as follows:
- choose the point 3, the first monster dies from a crusher trap at the point -1, the second monster dies from the explosion, the third monster is pushed to the point 7;
- choose the point 7, the third monster dies from the explosion.
In the second test case, Ivan acts as follows:
- choose the point 5, the first and fourth monsters die from the explosion, the second monster is pushed to the point 1, the third monster is pushed to the point 2;
- choose the point 2, the first monster dies from a crusher trap at the point 0, the second monster dies from the explosion.
每次从最后一个开始炸，贪心
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,r,a[maxn];
void solve(){
scanf("%d%d",&n,&r);
rep(i,1,n) scanf("%d",&a[i]);
sort(a+1,a+1+n);
n=unique(a+1,a+1+n)-a-1;
rep(i,1,n) if(a[n-i]-r*i<=0){
printf("%d\n",i);
return;
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C. Standard Free2play
time limit per test2 seconds memory limit per test256 megabyte
You are playing a game where your character should overcome different obstacles. The current problem is to come down from a cliff. The cliff has height h, and there is a moving platform on each height x from 1 to h.
Each platform is either hidden inside the cliff or moved out. At first, there are n moved out platforms on heights \(p_1, p_2, \dots, p_n\). The platform on height h is moved out (and the character is initially standing there).
If you character is standing on some moved out platform on height x, then he can pull a special lever, which switches the state of two platforms: on height x and x - 1. In other words, the platform you are currently standing on will hide in the cliff and the platform one unit below will change it state: it will hide if it was moved out or move out if it was hidden. In the second case, you will safely land on it. Note that this is the only way to move from one platform to another.
Your character is quite fragile, so it can safely fall from the height no more than 2. In other words falling from the platform x to platform x - 2 is okay, but falling from x to x - 3 (or lower) is certain death.
Sometimes it's not possible to come down from the cliff, but you can always buy (for donate currency) several magic crystals. Each magic crystal can be used to change the state of any single platform (except platform on height h, which is unaffected by the crystals). After being used, the crystal disappears.
What is the minimum number of magic crystal you need to buy to safely land on the 0 ground level?Input
The first line contains one integer q \((1 \le q \le 100)\) — the number of queries. Each query contains two lines and is independent of all other queries.
The first line of each query contains two integers h and n \((1 \le h \le 10^9, 1 \le n \le \min(h, 2 \cdot 10^5))\) — the height of the cliff and the number of moved out platforms.
The second line contains n integers \(p_1, p_2, \dots, p_n (h = p_1 > p_2 > \dots > p_n \ge 1) \)— the corresponding moved out platforms in the descending order of their heights.
The sum of n over all queries does not exceed \(2 \cdot 10^5\).Output
For each query print one integer — the minimum number of magic crystals you have to spend to safely come down on the ground level (with height 0).
Exampleinput
4 3 2 3 1 8 6 8 7 6 5 3 2 9 6 9 8 5 4 3 1 1 1 1
output
0 1 2 0
暴力模拟
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int h,n,a[maxn];
map<int,int> mp;
void solve(){
scanf("%d%d",&h,&n);
mp.clear();
dep(i,n,1) scanf("%d",&a[i]),mp[a[i]]=1;
int ans=0,now=h,pos=n;
while(1){
if(now<=2) break;
if(mp[now-1]==0){
if(a[pos]==now) now=a[--pos]+1;
else if(a[pos]<now){
now=a[pos]+1;
while(a[pos]>now) pos--;
}
}
else{
if(now-2<=0) break;
if(mp[now-2]==1){
now-=2;
while(a[pos]>now) pos--;
}
else{
now-=2;
while(a[pos]>now) pos--;
ans++;
}
}
}
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
D. AB-string
time limit per test2 seconds memory limit per test256 megabytes
The string \(t_1t_2 \dots t_k\) is good if each letter of this string belongs to at least one palindrome of length greater than 1.
A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not.
Here are some examples of good strings:
- ?t = AABBB (letters \(t_1, t_2\) belong to palindrome\( t_1 \dots t_2\) and letters \(t_3, t_4, t_5\) belong to palindrome \(t_3 \dots t_5)\);
- ?t = ABAA (letters \(t_1, t_2, t_3\) belong to palindrome \(t_1 \dots t_3\) and letter \(t_4\) belongs to palindrome \(t_3 \dots t_4)\);
- ?t = AAAAA (all letters belong to palindrome \(t_1 \dots t_5)\);
You are given a string ?s of length ?n, consisting of only letters A and B.
You have to calculate the number of good substrings of string ?s.Input
The first line contains one integer n \((1 \le n \le 3 \cdot 10^5)\) — the length of the string \(s\).
The second line contains the string s, consisting of letters A and B.Output
Print one integer — the number of good substrings of string s.
Examplesinput
5 AABBB
output
6
input
3 AAA
output
3
input
7 AAABABB
output
15
Not
In the first test case there are six good substrings: \(s_1 \dots s_2\), \(s_1 \dots s_4\), \(s_1 \dots s_5\), \(s_3 \dots s_4\), \(s_3 \dots s_5 \) and \(s_4 \dots s_5\).
In the second test case there are three good substrings: \(s_1 \dots s_2\),\( s_1 \dots s_3\) and \(s_2 \dots s_3\).
直接求答案比较困难，我们选择从所有子串中减去不符合条件的串：
容易发现，只有形如"ABBBB","BAAAA","BBBBA","AAAAB"的字符串才是不合法的，那么我们直接统计个数就可以了；
需要注意的是，比如AB这样的串，我们在删A...的时候删了一次，删...B的时候也删了一次，所以需要特殊处理一下
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
int n,cnt[maxn],pos;
char s[maxn];
int main(){
scanf("%d%s",&n,s+1);
s[n+1]='
;n++;
int cur=1;
rep(i,2,n){
if(s[i]==s[i-1]) cur++;
else{
cnt[++pos]=cur;
cur=1;
}
}
n--;
ll ans=1ll*n*(n-1)/2;
rep(i,1,pos){
// cout<<cnt[i]<<endl;
if(i>1) ans-=cnt[i]-1;
if(i<pos) ans-=cnt[i];
}
printf("%lld\n",ans);
}
E. Keyboard Purchase
time limit per test1 second memory limit per test256 megabyt
You have a password which you often type — a string s of length n. Every character of this string is one of the first m lowercase Latin letters.
Since you spend a lot of time typing it, you want to buy a new keyboard.
A keyboard is a permutation of the first m Latin letters. For example, if m = 3, then there are six possible keyboards: abc, acb, bac, bca, cab and cba.
Since you type your password with one finger, you need to spend time moving your finger from one password character to the next. The time to move from character\( s_i\) to character \(s_{i+1}\)is equal to the distance between these characters on keyboard. The total time you have to spend typing the password with a keyboard is called the slowness of this keyboard.
More formaly, the slowness of keyboard is equal to \(\sum\limits_{i=2}^{n} |pos_{s_{i-1}} - pos_{s_i} |\), where \(pos_x\) is position of letter x in keyboard.
For example, if s is aacabc and the keyboard is bac, then the total time of typing this password is \(|pos_a - pos_a| + |pos_a - pos_c| + |pos_c - pos_a| + |pos_a - pos_b| + |pos_b - pos_c|\) = \(|2 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 3|\) = \(0 + 1 + 1 + 1 + 2 = 5\).
Before buying a new keyboard you want to know the minimum possible slowness that the keyboard can have. Input
The first line contains two integers n and m \((1 \le n \le 10^5, 1 \le m \le 20)\).
The second line contains the string s consisting of n characters. Each character is one of the first m Latin letters (lowercase).Output
Print one integer – the minimum slowness a keyboard can have.
Examplesinput
6 3 aacabc
output
5
input
6 4 aaaaaa
output
0
input
15 4 abacabadabacaba
output
16
Note
The first test case is considered in the statement.
In the second test case the slowness of any keyboard is 00.
In the third test case one of the most suitable keyboards is bacd.
m只有20，脸上写着状压DP；
首先预处理出来所有的cnt[i][j]表示原串中相邻两个字母的对数；
dp[mk]表示当前确定键盘中填好了mk这个状态的那么多字母(顺序无所谓)时的答案，它可以转移到任意的mk|(1<<i)，其中(mk&(1<<i))==0；
那么显然对于i这个字母，它填的位置是num+1,其中num为mk中1的数量，也即目前键盘中已经填好的字母数量；
我们考虑已经填好m个字母的状态，那么对于一个字母i，它前面有一个字母j，这一对字母对于答案的贡献就是\(cnt[i][j]\times(pos_i-pos_j)\);
那么对于已经确定的i这个字母，之前没确定位置的j字母就可以分开处理，个人觉得这个是最精妙的对方；
对于一个之前没出现的字母\(j\)，\(i\)这个字母对于答案的贡献是\(-cnt[i][j]\times(num+1)\)，出现过的话就是\(+cnt[i][j]\times(num+1)\)，全部扫完后更新答案即可。
#include<bits/stdc++.h>
using namespace std;
#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 pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,m,cnt[21][21],dp[1<<21];
char s[maxn];
int main(){
scanf("%d%d%s",&n,&m,s+1);
rep(i,2,n) cnt[s[i-1]-'a'][s[i]-'a']++,cnt[s[i]-'a'][s[i-1]-'a']++;
rep(i,1,(1<<m)) dp[i]=INT_MAX;
rep(mk,0,(1<<m)-1-1){
int num= __builtin_popcount(mk);
rep(i,0,m-1) if((mk&(1<<i))==0){
int tmp=dp[mk];
rep(j,0,m-1){
if(i==j) continue;
if(mk&(1<<j)) tmp+=cnt[i][j]*(num+1);
else tmp-=cnt[i][j]*(num+1);
}
dp[mk|(1<<i)]=min(dp[mk|(1<<i)],tmp);
}
}
printf("%d\n",dp[(1<<m)-1]);
}
