Least Prefix Sum[贪心]
定义长度为 \(n\) 的数组 \(arr\) 的前缀和数组为 \(s\)，对于一次操作，你可以选择一个数，变为这个数的相反数，给定一个数 \(m\)，请你求出最小的操作次数使序列满足：\(\forall i\in[1,n], s_i\geq s_m\)。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 10,000 $ ). The description of the test cases follows.
The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \leq m \leq n \leq 2\cdot 10^5 $ ) — the size of Baltic's array and his favorite number.
The second line contains $ n $ integers $ a_1,a_2, \ldots, a_n $ ( $ -10^9 \leq a_i \leq 10^9 $ ) — the array.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .
输出格式
For each test case, print a single integer — the minimum number of required operations.
in
6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873
out
1
1
0
0
3
4
思路：
key code
const int N=2e5+10;
int n,m;
int a[N];
int s[N];
void solve(){
//try it again.
cin>>n>>m;
up(1,n)cin>>a[o];
up(1,n)s[o]=s[o-1]+a[o];
int minn=*min_element(s+1,s+1+n);
if(s[m]==minn){
cout<<0<<endl;
return;
}
int ans=0;
priority_queue<int>p;
int sum=0;
dn(m,2){
p.push(a[o]);
sum+=a[o];
while(sum>0){
ans++;
// debug(p.top());
sum-=p.top()*2;
p.pop();
}
}
priority_queue<int,vector<int>,greater<int>>q;
sum=0;
up(m+1,n){
q.push(a[o]);
sum+=a[o];
while(sum<0){
ans++;
// debug(q.top());
sum-=q.top()*2;
q.pop();
}
}
cout<<ans<<endl;
}
Interesting Sequence[位运算]
给两个数，\(n\) 和 \(x\)，问是否存在 \(m\)，使得 \(n \& n+1 \& …… \& m = x\)，如果存在求出最小的 \(m\)，否则输出 \(-1\)。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2000 $ ). The description of the test cases follows.
The only line of each test case contains two integers $ n $ , $ x $ ( $ 0\le n, x \le 10^{18} $ ).
输出格式
For every test case, output the smallest possible value of $ m $ such that equality holds.
If the equality does not hold for any $ m $ , print $ -1 $ instead.
We can show that if the required $ m $ exists, it does not exceed $ 5 \cdot 10^{18} $ .
in
5
10 8
10 10
10 42
20 16
1000000000000000000 0
out
12
10
-1
24
1152921504606846976
思路：
key code
void solve(){
//try it again.
cin>>n>>m;
if(m>n){
cout<<"-1"<<endl;
return;
}
if(m==n){
cout<<n<<endl;
return;
}
up(0,62){
if((((n>>o)&1)==0)&&(((m>>o)&1)==1)){
cout<<"-1"<<endl;
return;
}
}
int ans=0;
bool ok=true;
int pos=0;
dn(62,0){
if((((n>>o)&1)==1)&&(((m>>o)&1)==0)&&ok){
// debug((n>>o));
ok=false;
pos=o;
// ans|=(((int)(1)<<(o+1)));
}
if(!ok&&(((n>>o)&1)==1)&&(((m>>o)&1)==1)){
cout<<"-1"<<endl;
return;
}
}
if((1ll<<((pos+1))|n)==n){
cout<<"-1"<<endl;
return;
}
dn(63,pos+1){
if(n>>o&1)ans+=1ll<<o;
}
cout<<ans+(1ll<<(pos+1))<<endl;
}
Same Count One[构造]
给定 \(n\) 个长度为 \(m\) 的，只包含 \(0\) 和 \(1\) 的数组，选择任意两个数组交换位置 \(pos\) 上的数。在经过最少的操作后使得每个数组中的 \(1\) 数量相等，并输出操作过程。
输入格式
第一行一个整数 \(t\) \(( 1 \leq t \leq 2\cdot 10^4 )\) 表示有 \(t\) 组测试数据。
每组测试数据：第一行两个整数 $ n $ 和 $ m $ 。 $( 2 \leq n \leq 10^5 $ , $ 2 \leq m \leq 10^5 , \sum n\times m \le 10^6)$
接下来 $ n $ 行，每行 $ m $ 个整数（ $ 0 $ 或 $ 1 $ ）。
输出格式
对于每一组测试样例，若无法满足要求，输出 $ -1 $ .
否则, 第一行输出一个整数 $ k $ $ (0 \le k \le mn) $ ，即最小的操作数量。
接下来输出 $ k $ 行，每行 $ 3 $ 个整数, $ x, y, z $ $ (1 \le x, y \le n, 1 \le z \le m) $ , 表示交换 $ a_{x, z}, a_{y, z} $ : 即交换第 $ x $ 和第 $ y $ 行的第 $ z $ 个数。
in
3
3 4
1 1 1 0
0 0 1 0
1 0 0 1
4 3
1 0 0
0 1 1
0 0 1
0 0 0
2 2
0 0
0 1
out
1
2 1 1
1
4 2 2
-1
思路
显然这是一个贪心，如果有不能整分的情况就是-1
然后按列进行贪，贪完了就是胜利
key code
void solve(){
//try it again.
cin>>n>>m;
int sum=0;
vector<vector<int>>a(n,vector<int>(m));
vector<int>cntx(m);
vector<int>cnty(n);
fup(i,0,n-1){
fup(j,0,m-1){
cin>>a[i][j];
sum+=a[i][j];
}
}
if(sum%n){
cout<<-1<<endl;
return;
}
int cnt=sum/n;
int test=0;
fup(i,0,n-1){
fup(j,0,m-1){
cntx[j]+=a[i][j];
cnty[i]+=a[i][j];
}
}
vector<tuple<int,int,int>>ans;
vector<int>T1;
vector<int>T2;
fup(j,0,m-1){
fup(i,0,n-1){
if(cnty[i]>cnt&&a[i][j]){
T1.pb(i);
}
if(cnty[i]<cnt&&!a[i][j]){
T2.pb(i);
}
}
fup(i,0,min((int)(T1.size()-1ll),(int)(T2.size()-1ll))){
ans.pb(T1[i],T2[i],j);
cnty[T1[i]]--;
cnty[T2[i]]++;
}
T1.clear();
T2.clear();
}
cout<<ans.size()<<endl;
for(auto [i,j,k]:ans){
cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
}
}
Permutation Game[博弈]
有一个长度为 \(n\) 的仅为 \(1\sim n\) 的序列，初始序列中所有的数均为红色。两个玩家依次进行以下三种操作中一种：
- 将某个数变成蓝色。
- 将所有蓝色的数重新排列（按照自己的意愿排列，红色不可进行排列，不必将所有的蓝色都交换位置）。
- 跳过此次操作。
两个玩家依次进行一次操作视为一个回合，游戏共进行 \(100^{500}\) 回合。在游戏任何时刻，如果当前序列为 \(\{1,2,3...,n\}\)，则第一个操作的玩家胜利。如果当前序列为 \(\{n,n-1,n-2...1\}\)，则第二个玩家胜利。进行 \(100^{500}\) 回合之后若还无人胜利，则平局。注意，两名玩家都以最优方案进行操作。他们会尽可能让自己胜利。
输入格式
第一个数为 \(t\)（\(1\le t\le10^5\)）表示数据组数。
对于每一组数据，第一行一个数 \(n\)，表示序列长度，下一行 \(n\) 个数表示初始序列。
输出格式
如果第一个操作玩家胜利，输出 First ，如果第二个玩家操作胜利，输出 Second，平局输出 Tie。
in
4
4
1 2 4 3
3
2 3 1
5
3 4 5 2 1
6
1 5 6 3 2 4
out
First
Tie
Second
Tie
思路：
我们设\(a\)为第一个玩家需要单独操作的次数，\(b\)为第二个玩家需要单独操作的次数，\(c\)为两个个玩家都需要操作的次数
易知第一个玩家想要获胜必须要满足\(a+c \le b\)
第二个玩家想要获胜必须要满足\(b+c < a\)
否则就是平局
博弈题难得就是情况的分析和判断
key code
void solve(){
//try it again.
cin>>n;
up(1,n)cin>>a[o];
int ans1=0;
int ans2=0;
int ans3=0;
up(1,n){
if(a[o]!=o)ans1++;
}
up(1,n){
if(a[o]!=(n-o+1))ans2++;
}
up(1,n){
if(a[o]!=o&&a[o]!=(n-o+1))ans3++;
}
// ans1++;
// ans2++;
// debug3(ans1,ans2,ans3);
if(ans1+ans3<=ans2){
cout<<"First\n";
}
else if(ans2+ans3<ans1){
cout<<"Second\n";
}
else cout<<"Tie\n";
}
Hossam and Trainees[数学]
有 \(T\) 组数据，每组数据给出 \(n\) 和长度为 \(n\) 的数列 \(a_i\)，判断有没有两个数不互质，如果有输出 "YES"，没有输出 "NO"
输入格式
The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^5 $ ), the number of test cases. Description of the test cases follows.
The first line of each test case contains an integer number $ n $ ( $ 2 \le n \le 10^5 $ ).
The second line of each test case contains $ n $ integers, the number of each trainee $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ).
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式
Print the answer — "YES" (without quotes) if there is a successful pair of trainees and "NO" otherwise. You can print each letter in any case.
in
2
3
32 48 7
3
14 5 9
out
YES
NO
思路
那么这个题我们很容易就想到遍历一遍看有没有\(gcd(a,b) \neq 1\)的情况
但是看到$ 2 \le n \le 10^5 $ 又只能作罢
然后我们可以想到分解因子的方法
又因为$ 1 \le a_i \le 10^9 $
所以\(a_i\)大于\(\sqrt{10^9}\)的因子只有一个
再用线性筛判断一遍即可
key code
const int N=2e5+10;
const int M=35020;
int n,m;
int primes[M], cnt; // primes[]存储所有素数
bool st[M]; // st[x]存储x是否被筛掉
int num[M];
int a[N];
map<int,int>mp;
void get_primes(int n){
for (int i = 2; i <= n; i ++ ){
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ ){
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void solve(){
//try it again.
cin>>n;
mp.clear();
up(1,n)cin>>a[o];
memset(num,0,sizeof(int)*35000);
fup(i,1,n){
for(int j=0;j<cnt&&primes[j]<=a[i];j++){
if(a[i]%primes[j]==0){
num[j]++;
if(num[j]>1)YES
while(a[i]%primes[j]==0)a[i]/=primes[j];
}
}
if(a[i]>1){
mp[a[i]]++;
if(mp[a[i]]>1)YES
}
}
NO
}
signed main(){
IOS;
get_primes(35000);
int __;
cin>>__;
while(__--)
solve();
return 0;
}
Koxia and Number Theory[数学]
对于每组数据，给你一个长度为 \(n\) 的数组 \(a\) ，要你找到一个 \(x>0\) 使得对于每个 \(i,j\ (1\le i< j\le n)\) 都有 \(a_i+x\) 与 \(a_j+x\) 互质。
输入的第一行是一个整数 \(t\ (1≤t≤100 )\) ，表示有 \(t\) 组数据。
对于每组数据，第一行是一个整数 \(n\ (2≤n≤100 )\) ，表示数组 \(a )\) 的长度。
接下来 \(n\) 个整数，表示数组 \(a\ (1≤a_i≤10^{18})\) 。
共 \(t\) 行，第 \(i\) 行表示第 \(i\) 组数组是否能找到 \(x\) ，若能，输出"YES"，否则输出"NO"。
输入格式
Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of test cases follows.
The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 100 $ ) — the size of the array.
The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq {10}^{18} $ ).
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ .
输出格式
For each test case, output "YES" (without quotes) if there exists a positive integer $ x $ such that $ \gcd(a_i+x,a_j+x)=1 $ for all $ 1 \leq i < j \leq n $ , and "NO" (without quotes) otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
in
2
3
5 7 10
3
3 3 4
out
YES
NO
思路
这个题是问能不能给出一个数使得数组加上这一个数以后数组中的数全部互质
我们先判断特殊的情况
当有两个数是相等的情况那么就不存在，因为无论加多少这两个数都不互质
我们想象如果有2个奇数，2个偶数，那么无论加多少都会有两个偶数，此时也不互质
如果有2个模3得0的，2个模3得1的，2个模3得2的，那无论加多少都会存在两个可以被3整除的数
由此我们可以类推
如果存在一个值使得模他的每一个值都有两个或以上的数组元素对应那么就无法获得全部互质的数列
由于数组的长度最长为100，那么我们就可以开一个\(f[110][110]\)的数组来记录
key code
const int N=110;
int n,m;
int a[N];
int f[N][N];
void solve(){
//try it again.
cin>>n;
map<int,int>mp;
mem0(f);
up(1,n)cin>>a[o];
up(1,n){mp[a[o]]++;if(mp[a[o]]>1)NO}
up(1,n){
fup(i,1,n){
f[i][a[o]%i]++;
}
}
up(2,n){
bool falg=true;
fup(i,0,o-1){
if(f[o][i]<2){falg=false;break;}
}
if(falg)NO
}
YES
}
Lucky Chains[数学]
- 给出两个正整数 \((x,y)\)，满足 \((x,y),(x+1,y+1),(x+2,y+2),\dots,(x+k,y+k)\) 都是互质的，直到 \((x+k+1,y+k+1)\) 起不互质
- 问 \(k\) 的值，或指出这个互质的序列长度为 \(0\) 或是无限长的
输入格式
The first line contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the number of pairs.
Next $ n $ lines contains $ n $ pairs — one per line. The $ i $ -th line contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i < y_i \le 10^7 $ ) — the corresponding pair.
输出格式
Print $ n $ integers, where the $ i $ -th integer is the length of the longest lucky chain induced by $ (x_i, y_i) $ or $ -1 $ if the chain can be infinitely long.
in
4
5 15
13 37
8 9
10009 20000
out
0
1
-1
79
思路：
题目给出\(n\)和\(m\)，要找到最小的\(k\)使得\(n+k\)和\(m+k\)有公因数
我们假设\(n+k\)是\(p\)的倍数
那么\(m+k\)也是\(p\)的倍数
易知\(m-n\)也是\(p\)的倍数
设\(x\)\(=m-n\)
那么就是求\(x\)与\(n+k\)存在公因数 的最小的\(k\)
然后我们给\(x\)筛质数，然后求就行了
key code
const int N=1e4+10;
int n,m;
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void solve(){
//try it again.
cin>>n>>m;
int k=m-n;
if(k==1){cout<<-1<<endl;return;}
vector<int>ans;
if(__gcd(n,m)!=1){
cout<<0<<endl;
return;
}
fup(it,0,cnt-1){
if(k%primes[it]==0){
ans.pb(primes[it]);
while(k%primes[it]==0)k/=primes[it];
if(k>1)ans.pb(k);
}
if(k<primes[it])break;
}
if(k!=1)ans.pb(k);
int last=INF;
for(auto it:ans){
int res=it-n%it;
last=min(last,res);
}
cout<<last<<endl;
}
signed main(){
IOS;
get_primes(5010);
int __;
cin>>__;
while(__--)
solve();
return 0;
}
Watch the Videos[双指针]
有 $ n $ 个视频，第 $ i $ 个视频的大小为 $ a_i $。你有一块容量为 $ m $ 的硬盘。每一个视频必须先花费 $ a_i $ 的时间下载下来，保存在硬盘里（占据硬盘 $ a_i $ 的空间），才能观看。观看一个视频花费的时间为 $ 1 $。
此外，还有几个注意点：
一、任何时候，硬盘被占据的空间必须小于等于 $ m $。
二、一个视频在看完之后可以立刻删除，把占据的 $ a_i $ 的空间释放掉。删除这件事情不需要花费时间。
三、不能同时下载超过一个视频，也不能同时观看超过一个视频。但是可以在下载某个视频的同时，观看其他已经保存在硬盘里的视频。
你可以按任何顺序下载和观看这 $ n $ 个视频，问看完所有视频，最少需要花费多长时间。
$ 1 $ \({\leq}\) $ n $ \({\leq}\) $ 2 * 10 ^ 5 \(；\) 1 $ \({\leq}\) $ m $ \({\leq}\) $ 10 ^ 9 \(；\) 1 $ \({\leq}\) $ a_i $ \({\leq}\) $ m $
输入格式
The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le m \le 10^9 $ ) — the number of videos Monocarp wants to watch and the size of the hard disk, respectively.
The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le m $ ) — the sizes of the videos.
输出格式
Print one integer — the minimum time required to watch all $ n $ videos.
in
5 6
1 2 3 4 5
out
16
in
5 5
1 2 3 4 5
out
17
in
4 3
1 3 2 3
out
12
思路：
思路就是所有的下载时间都是无法省略的
但是我们可以在下载的时候观看电影来节省时间
一定有一种最优方案，满足在任意时刻，硬盘里不超过两个视频。证明：假设在硬盘里本来有一个视频，新下载一个视频的时候可以把本来的这个视频观看掉，然后立刻删除（删除视频一定不会使答案变劣）。也就是说，只要硬盘里有两个视频，一定有一个视频可以在另一个视频下载的时候被观看掉。
那只要满足这个关系就可以省下一次的观影时间
key code
const int N=2e5+10;
int n,m;
int a[N];
void solve(){
//try it again.
cin>>n>>m;
up(1,n)cin>>a[o];
int sum=n;
up(1,n){
sum+=a[o];
}
sort(a+1,a+1+n);
int l=1,r=n;
while(l<r){
if(a[l]+a[r]<=m)l++,sum-=l<r?2:1;
r--;
}
cout<<sum<<endl;
}