圖像壓縮

曾經看到過，這是一道洛谷原題，很可惜我沒做過，有點看不懂就沒嘗試。

原題鏈接：B3851 [GESP202306 四級] 圖像壓縮 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

因數分解

直接枚舉就行了，從2開始找因子，到sqrt（n），從小到大能被除的話一定是素數。

假設a<b<c，且a和c是素數因子，b是合數因子。

由于合數可以由素數因子相乘得到：那么b=d+e，且d和e均小于等于sqrt(b)，故從2到sqrt(n)遍歷能除的除干凈之后，除出來的必然是素數。

對于大于sqrt(n)部分的因子，合數因子必然能分解成小于sqrt(n)的部分，除完之后還有剩下的，那么剩下的就為素數。

Q：有沒有可能剩下的素數有兩個。

A：兩個素數均大于sqrt(n)，則乘積大于n，不合法。故最多一個。

最后考慮特殊情況，如果上面循環完了n還不為1，那么n就是素數。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define fr first
#define se second
#define endl '\n'
using namespace std;void solve(){int n;cin>>n;map<int,int>f;int a=n;per(i,2,sqrt(n)){if(a%i==0){int cnt=0;while(a%i==0){a/=i;cnt++;}f[i]=cnt;}}if(a>1)f[a]++;auto it=f.rbegin();for(auto i:f){if(i.se==1){cout<<i.fr<<" ";}else{cout<<i.fr<<"^"<<i.se<<" ";}if(i!=*it){cout<<"* ";}}
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}

一個數可以分解數質數相乘。

更細化的，這些質數可以是偶數個或者奇數個。如 2 * 3 都只有一個，而 2^2*3，2有兩個。

所以我們可以把質數分成 數量為奇數的 和 數量為偶數的。

根據從小到大能除除干凈，除出來的是質數，我們可以先分離出數量為偶數的。

    per(i,2,sqrt(n)){int x=i*i;while(n%x==0)f[i]+=2,n/=x;}

假設一個平方質因子都沒分離出來，那么n=a*b*c*d a,b,c,d為素數且均為一個。

所以只需要2~sqrt(n)遍歷一次，大于sqrt(n)的只有一個，故如果n除完之后大于1，這就是那一個大于sqrt的數。

總復雜度sqrt(n)+sqrt(n)，但是這樣可以分離出所有的單個因子，有需要的話可以提供更多思路。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define fr first
#define se second
#define endl '\n'
using namespace std;void solve(){int n;cin>>n;map<int,int>f;per(i,2,sqrt(n)){int x=i*i;while(n%x==0)f[i]+=2,n/=x;}per(i,2,sqrt(n)){if(n%i==0){f[i]++;n/=i;}}if(n>1)f[n]++;auto it=f.rbegin();for(auto i:f){if(i.se>=2){cout<<i.fr<<"^"<<i.se<<" ";}else cout<<i.fr<<" ";if(i!=*it){cout<<"* ";}}
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}

探險

這道題應該才是簽到題。不過被榜單帶歪了都是先做的 因數分解 和 求和。

可以肯定的是，小理一定在某個洞穴停下，剩下的次數全部用來反復進入前面進入過的洞穴，且反復進入的洞穴一定是同一個，經驗值最大的那一個。

那么只需要枚舉所有情況就可以了。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define fr first
#define se second
#define endl '\n'
using namespace std;void solve(){int n,k;cin>>n>>k;vector<int> a(n+1),b(n+1);per(i,1,n)cin>>a[i];per(i,1,n)cin>>b[i];int f=0,res=0,ans=0;per(i,1,min(n,k)){int leave=k-i;//剩下的次數f+=a[i];//開洞穴累計的經驗值res=max(res,b[i]);//前面開過的洞穴最大的那一個ans=max(ans,leave*res+f);//累計答案}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;cin>>t;while(t--)solve();return 0;
}

最小乘積

這道題顯然官方數據集弄錯了，導致一個人都沒有通過。

可以進行的操作：

1、ai<0 可以將 ai 替換成 [ai,0] 其中的一個。

2、ai>=0 可以將 ai 替換成 [0，ai] 其中的一個。（顯然 0 不能做修改）

要求進行最少的操作，使得數組的乘積最小。

只需要記錄一下正數，負數，0，的數量即可。

如果存在 0，顯然不管怎么操作最后乘積都是0，則不需要操作。

如果不存在 0，若?負數 有奇數個，那么最終乘積為負數，不需要修改。

? ? ? ? ? ? ? ? ? ? ? ? ?若 負數 有偶數個，那么乘積一定正數，任意一個改成0。

無人AC。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define fr first
#define se second
#define endl '\n'
using namespace std;void solve(){int n;cin>>n;int pos=0,neg=0,zero=0;per(i,1,n){int tmp;cin>>tmp;if(tmp>0)pos++;else if(tmp<0)neg++;else if(tmp==0)zero++;}if(zero){cout<<0<<endl;}else{if(neg%2==0){cout<<1<<endl;cout<<1<<" "<<0<<endl;}else{cout<<0<<endl;}}
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;cin>>t;while(t--)solve();return 0;
}

若此非正解請在評論區留言，否則建議大伙避雷該比賽，且本次全國賽算法科目只有120個左右參加，好少的人。

求和

一道哈人的模擬題。

思路比較簡單，就是數字全部提取出來加在一起。

需要注意的是負號-，有可能作為分隔符使用。

如2-3，輸出的是2+3=5

而2--3，輸出的是2-3=-1

那么作為分割符的條件就很明顯了，前面不能是數字。

由于輸入沒有告知多少行，且中間可能存在空行，所以我們使用getline來讀入。

string s;
while(getline(cin,s))

本地調試的時候如果沒有結果，請按下Ctrl+D，相當于輸入文件末尾的EOF。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define debug(a) cout<<#a<<"="<<a<<endl
#define fr first
#define se second
#define endl '\n'
using namespace std;void solve(){string s;while(getline(cin,s)){int res=0,ans=0;bool havNum=false;int pos=1;//是否是正數if(s.empty())continue;//什么都沒有輸入直接跳過per(i,0,s.length()-1){if(s[i]>='0' and s[i]<='9'){havNum=true;res*=10;res+=s[i]-'0';}else if(s[i]=='-' and s[i+1]>='0' and s[i+1]<='9' and !(s[i-1]>='0' and s[i-1]<='9')){pos=-1;}else{
//                debug(res*pos);ans+=res*pos;pos=true;res=0;}}if(res)ans+=res*pos;//考慮最后結尾是數字，沒有累加上的情況。if(havNum)cout<<ans<<endl;//字符串中至少有一個整數才能輸出。}
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}