|
（今天场队友带飞
C.LCS
题目大意：构造三个长度为n的字符串，使得两两最长公共子序列为x,y,z
思路：假设x>=y>=z，分别对应s1s2,s2s3,s3s1
当x+y-n > z时无解，当x+y-n>0时s1s3必有交集，也就是说x+y-n是s1s3的最小交集
先给三个字符串加上z个a的前缀，问题转化成(x-z)+(y-z)<=n-z，给s1s2加上x-z个连续的b，给s2s3加上连续的c即可，其他多的地方构造成不等的就行
F.just a joke
（我才是joker = =
题意：无向图删边游戏，每次可以删一条边或者一个无环连通块
思路：看点数、边数奇偶
删边操作即删去一条边，删连通块等价于删去k个点和（k-1）条边，看点数和边数奇偶即可
（无语了，一开始还想着缩点找环。。。还是没看透问题的本质唉，结论也是猜的，不会证。。
I.Inverse pair
题目大意：给定一个排列，先可以对每个数加1或者不加，求操作后的最小逆序对数
思路：简单贪心，如果x+1在x前面位置，我们就给它加1，这样对总逆序对的贡献是-1，最后树状数组算一下逆序对即可
J，average
题目大意：本质就是求给定两串数n,m，分别求最大平均值的区间，区间长度至少为x,y
思路：二分平均值即可（显然满足单调性，但是一开始不会写，就去二分长度wa了），还有O(n)斜率优化的做法，队友拉了板子过掉了
记录一下二分double的写法（之前记录的不知道丢哪去了）
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
using namespace std;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pb push_back
#define IOS ios::sync_with_stdio(false)
#define int long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define all(v) v.begin(),v.end()
typedef long long ll;
const int N=1e5+10;
int a[N],b[N],c[N];
int suma[N];
int sum1,sum2;
int n,m,x,y;
double ans,res;
bool check(int a[],int n, double mid ,int x)
{
double c[N] = {0};
double sum[N] = {0};
_for(i,1,n)
{
c[i] = a[i] - mid;
sum[i] = sum[i-1] + c[i];
}
double mi=inf;
_for(i,x,n)
{
mi = min(mi,sum[i-x]);
if( sum[i] >=mi ) return true;
}
return false;
}
double query(int a[] ,int n,int x)
{
double l=1,r=1e5+10;
_for(i,1,60)
{
double mid = (l+r)/2;
if( check(a,n,mid,x) ) l=mid;
else r=mid;
}
return l;
}
void solve()
{
printf("%.10lf\n",query(a,n,x)+query(b,m,y));
}
signed main()
{
// !!!
// freopen("data.txt","r",stdin);
// !!!
// IOS;
scanf("%lld %lld %lld %lld",&n,&m,&x,&y);
_for(i,1,n) scanf("%lld",&a[i]);
_for(i,1,m) scanf("%lld",&b[i]);
solve();
}
|