前言：T3写挂了，有点难受。
---------------
T1 中位数
题意简述:给你一段长度为$n$的序列，分别输出$[1,2k-1]$的中位数$(2k-1\leq n)$。
-------------
其实正解是用两个堆分别为大根堆和小根堆。但我这里偷了个懒，直接由STL函数upper_bound二分查找插入数字（STL大法好
Code:
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int n;
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
v.insert(upper_bound(v.begin(),v.end(),x),x);
if (i%==)
printf("%d\n",v[(i-)/]);
}
return ;
}
T2 多边形
题意简述:给你一个有n个边的多边形,每个顶点上有一个数字,每条边上为$+$或$\times $ .现在去掉任意一条边,求运算的最大值.
--------------
这道题其实跟石子合并有点像,不过有一点要注意:1.子区间的合并受运算符号限制;2.可能有负数,所以我们同时要维护最小值,因为有可能负乘负大于当前数.
题目细节较多.
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int f[maxn*][maxn*][maxn*],mf[maxn*][maxn*][maxn*];
int ch[maxn*],a[maxn*];
int n,ans=-0x3f3f3f3f;
int maxx(int a,int b,int c,int d,int e)
{
return max(a,max(b,max(c,max(d,e))));
}
int minn(int a,int b,int c,int d,int e)
{
return min(a,min(b,min(c,min(d,e))));
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
for (int j=;j<=n*;j++)
for (int k=;k<=n*;k++) f[i][j][k]=-0x3f3f3f3f,mf[i][j][k]=0x3f3f3f3f;
for (int i=;i<=*n;i++)
{
if (i%==){
char c;cin>>c;
if (c=='t') ch[i/+]=;
else ch[i/+]=;
}
else cin>>a[i/];
}
for (int i=n+;i<=n*;i++)
{
a[i]=a[i-n];
ch[i]=ch[i-n];
}
for (int i=;i<=n;i++)
for (int j=;j<=n*;j++) f[i][j][j]=mf[i][j][j]=a[j];
for (int i=;i<=n;i++)
{
for (int len=;len<=n;len++)
{
for (int j=i;j<=i+n-;j++)
{
int k=j+len-;
if (k>=i+n) break;
for (int l=j;l<k;l++)
{
if (ch[l+]==) {
f[i][j][k]=max(f[i][j][k],f[i][j][l]+f[i][l+][k]);
mf[i][j][k]=min(mf[i][j][k],mf[i][j][l]+mf[i][l+][k]);
}
else{
f[i][j][k]=maxx(f[i][j][k],f[i][j][l]*f[i][l+][k],f[i][j][l]*mf[i][l+][k],mf[i][j][l]*f[i][l+][k],mf[i][j][l]*mf[i][l+][k]);
mf[i][j][k]=minn(mf[i][j][k],f[i][j][l]*f[i][l+][k],f[i][j][l]*mf[i][l+][k],mf[i][j][l]*f[i][l+][k],mf[i][j][l]*mf[i][l+][k]);
}
}
}
}
ans=max(ans,f[i][i][i+n-]);
}
printf("%d",ans);
return ;
}
T3 连锁店
题意简述:张三开了$n$个连锁店,每个连锁店能用$a_{i}$个空瓶换$b_{i}$瓶水.每个店都可以无限次兑换,现在李四有$s$瓶水,求最多的兑换次数.如果不存在输出$-1$.
$n\leq 100000$,$s,a_{i},b_{i}\leq 10^{19}$.
---------------------
无解的情况:当$s\geq a_{i}$并且$a_{i}\leq b_{i}$.在输入的时候顺便判断.
我们考虑贪心:以$a_{i}-b_{i}$作为关键字排序很显然差值越小,兑换次数越多.
记得开$unsigned$ $long$ $long$.
Code:
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 1e5+,mod = 1e9+;
struct node{ll x,y,z;}a[maxn];
bool operator < (const node a,const node b){
if(a.z != b.z)return a.z < b.z;
return a.x<b.x;
}
int main()
{
int n,flag = ; ll s,ans = ;
scanf("%d%llu",&n,&s);
for(int i=;i<n;i++){
scanf("%llu%llu",&a[i].x,&a[i].y);
if(a[i].x>s)n--,i--;
else if(a[i].x<=a[i].y)flag = ;
a[i].z = a[i].x-a[i].y;
}
if(flag)return *puts("-1");
sort(a,a+n);
for(int i=;i<n;i++){
if(s>=a[i].x){
ll tmp = (s-a[i].x)/a[i].z+;
ans += tmp;
s -= tmp*a[i].z;
}
printf("%llu\n",ans);
return ;
}