Photo by NO NAME from Pixels
对m/n不断除以3，再除以2即可
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
int n,m;
cin>>n>>m;
int ans=0;
if(n==m){
ans=0;
}else if(m%n!=0){
ans=-1;
}else{
int tmp=m/n;
while(tmp%3==0){
ans++;
tmp/=3;
}
while(tmp%2==0){
ans++;
tmp/=2;
}
if(tmp!=1)
ans=-1;
}
cout<<ans<<endl;
return 0;
} 对于一个序列，设从左端开始的最长1序列的长度为len1，从右端开始的最长1序列的长度为len2，处于序列中间的最长1序列的长度为len3,最长的连续1序列的长度只可能是len3或len1+len2.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int arr[2*maxn];
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
int len1,len2;int len3;
len1=len2=len3=0;
for(int i=1;i<=n;i++){
if(arr[i]==0)
break;
len1++;
}
for(int i=n;i>=1;i--){
if(arr[i]==0)
break;
len2++;
}
// int beg,end;
int tmp=0;
for(int i=1;i<=n;i++){
if(arr[i]==0){
tmp=0;
len3=max(len3,tmp);
continue;
}
tmp++;
len3=max(len3,tmp);
}
// cout<<"len3="<<len3<<endl;
int ans=max(len3,len1+len2);
cout<<ans<<endl;
return 0;
}题意是说，存在一个序列\(p\)和序列\(q\)，且p是一个\(1~n\)的排列（就是说\(1~n\)这n个数都必须出现且只能出现一次），对于\(q_i\)，有\(q_i=p_{i+1}-p_i\)，即\(p_i+q_i=p_{i+1}\)。现在只给出q，让我们求出p。
分析后不难得出以下思路：我们可以先假设\(p_1=1\)，并根据\(q_i=p_{i+1}-p_i\)得出一段q序列，并找到该序列的最小值。该最小值正好对应的就是我们要求的\(p\)序列中的1，因此我们可以将现在的得到的p序列中的每一个值都加上1到当前最小值的差值，最后再用一个vis数组判断以下每个数的出现次数，即可得到答案。（转化为图像的话会更好理解）
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int arr[maxn*2];
int seq[maxn*2];
int ans[maxn*2];
map<int,int> vis;
int main()
{
// freopen("data_generator.txt","r",stdin);
int n;cin>>n;
for(int i=1;i<n;i++)
cin>>arr[i];
bool flag=1;
int mini=0;
int tmp=0;
seq[1]=0;
for(int i=1;i<n;i++){
seq[i+1]=tmp=seq[i]+arr[i];
if(vis.count(tmp)){
flag=0;
break;
}
vis[tmp]=1;
if(tmp<mini){
mini=tmp;
}
}
vis.clear();
int raise=(mini<=1?1-mini:mini-1);
for(int i=1;i<=n;i++){
ans[i]=seq[i]+raise;
vis[ans[i]]++;
}
// debug;
for(int i=1;i<=n;i++){
if(vis[i]!=1){
flag=0;
break;
}
}
if(flag){
for(int i=1;i<=n;i++)
printf("%d%c",ans[i],i==n?'\n':' ');
}else{
printf("-1\n");
}
return 0;
}题意是说对于两个字符串，每个字母代表一种颜色，两个相同的字母可以凑成一对，问如果从字符串一中挑出一个字符、再从字符串二中挑出一个字符（挑出后不放回），最多能凑出多少对。如果字符为'?'，说明该字符可以与任何字符配对（包括'?'）
暴力贪心即可😀
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=150000+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
vector<int> lef[128];
vector<int> rig[128];
struct node{
int lef_boot;
int rig_boot;
};
node ans[maxn];
int main()
{
int n;cin>>n;
string l,r;
cin>>l>>r;
for(int i=0;i<n;i++){
lef[l[i]].push_back(i+1);
rig[r[i]].push_back(i+1);
}
int cnt=0;
for(int i=97;i<=122;i++){
while(!lef[i].empty()&&!rig[i].empty()){
ans[cnt++]=node{lef[i].back(),rig[i].back()};
lef[i].pop_back();
rig[i].pop_back();
}
}
for(int i=97;i<=122;i++){
while(!lef['?'].empty()&&!rig[i].empty()){
ans[cnt++]=node{lef['?'].back(),rig[i].back()};
lef['?'].pop_back();rig[i].pop_back();
}
if(lef['?'].empty()) break;
}
for(int i=97;i<=122;i++){
while(!rig['?'].empty()&&!lef[i].empty()){
ans[cnt++]=node{lef[i].back(),rig['?'].back()};
rig['?'].pop_back();lef[i].pop_back();
}
if(rig['?'].empty()) break;
}
while(!lef['?'].empty()&&!rig['?'].empty()){
ans[cnt++]=node{lef['?'].back(),rig['?'].back()};
lef['?'].pop_back();rig['?'].pop_back();
}
printf("%d\n",cnt);
for(int i=0;i<cnt;i++) printf("%d %d\n",ans[i].lef_boot,ans[i].rig_boot);
return 0;
}题意是说，对于一个序列，每一个元素都包含\(t_i\)和\(b_i\)两个值，现在要求一个长度不超过\(k\)的子序列，使得该序列中的值满足\(\Sigma\ t_i\times \ min(b_i)\)的值最大。
emmmmmm一开始我是用的dp，因为感觉这题很像01背包，如果把k看作是背包总容量，每个元素的体积是1的话......但事实是我搞不出来OTZ......然后就去看题解了OTZ
正确做法是贪心。因为我们要求的是\(\Sigma\ t_i\times \ min(b_i)\)的最大值，而要让该值最大，我们应该贪心地选择更大的\(t_i\)。具体来说就是，先对所有元素按照\(b\)值从小到大排个序，然后从左到右扫描这些元素（排序的目的是为了保证扫过去时取到的\(b_i\)一定不大于上一次取到的\(b_i\)，也就是保证取得最小的\(b_i\)），然后在这个过程中，用优先队列维护\(t\)值前k大的元素。在选择元素的过程中，如果当前被选元素的个数大于\(k\)，就把队列中\(t\)值最小的pop出去，并更新答案。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node{
int t,b;
bool operator<(const node& nb){
return b<nb.b;
}
};
node ns[3*maxn];
priority_queue<int,vector<int>,greater<int>> que;
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>ns[i].t>>ns[i].b;
sort(ns+1,ns+n+1);
ll ans=-1;ll sum=0;
for(int i=n;i>=1;i--){
sum+=ns[i].t;
que.push(ns[i].t);
while(que.size()>k){
sum-=que.top();
que.pop();
}
ans=max(ans,sum*ns[i].b);
}
cout<<ans<<endl;
return 0;
}(或许这题确实能用dp吧......)
题意是说，对于一个多边形，首先按顺时针顺序从1开始对顶点进行排序。然后我们将他分割成若干个不重叠的三角形，并规定，对于每个三角形，其权重为三个顶点的序号的乘积。问如何分割该多边形可以使得其三角形权重和最小。
emmmmm......大水题
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
IOS;
ll ans=1;
int n;cin>>n;
if(n==3){
ans=6;
}else if(n==4){
ans=18;
}else{
ans=0;
for(ll i=2;i<n;i++)
ans+=i*(i+1);
}
cout<<ans<<endl;
return 0;
}emmmmm也是大水题
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
int n;cin>>n;
string str;
cin>>str;
int ans=0;int cnt=0;
for(int i=0;i<str.size();i++){
int tmp=str[i]-'0';
if(tmp%2==0)
ans+=i+1;
}
cout<<ans<<endl;
return 0;
} 题意是说对于一个序列\(a_n\),可以从第i个位置取出\(x_i(x_i<=a_i)\)，从而形成一个新的序列\(x_n\)，该序列必须满足以下两个条件中至少一个:
- \(x_i=0\)
- 若\(i<j\)，则\(x_i<x_j\)
依然是大水题......
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll arr[maxn<<1];
int main()
{
IOS;
ll n;cin>>n;
for(ll i=1;i<=n;i++)
cin>>arr[i];
ll ans=0;
ans+=arr[n];ll tmp=arr[n];
for(ll i=n-1;i>=1;i--){
if(arr[i]<tmp){
tmp=arr[i];
ans+=arr[i];
}else{
if(tmp-1>0)
tmp--;
else
tmp=0;
ans+=tmp;
}
}
cout<<ans<<endl;
return 0;
}