King of Range
题意
题目是让我们找到一段序列中所有的区间，满足区间最大值和区间最小值的差大于k
题解
这道题我们可以用单调队列和st表解决
st表，直接爆搜整个区间，找到区间内最短的满足的长度，相加就好了
单调队列
对于单调队列，我们可以用两个单调队列一个单增一个单减，单增的队列维护最小值，但减的序列维护最大值，然后弹出最前面的，找到离我们当前区间最近的满足的，逐个计算，由于首位置不同不会重复
注意是要弹出找到最近的满足的；
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int maxx[N], minn[N], a[N];
int n, m, k;
long long ans;
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
while (m--) {
int mil = 1, mxl = 1, mir = 0, mxr = 0;
cin >> k;
ans = 0;
for (int i = 1,last=0; i <= n; i++) {
while (mil <= mir && a[minn[mir]] >= a[i])mir--;
minn[++mir] = i;
while (mxl <= mxr && a[maxx[mxr]] <= a[i])mxr--;
maxx[++mxr] = i;
while (mil <= mir && mxl <= mxr && a[maxx[mxl]] - a[minn[mil]] > k) {
if (mil <= mir && (mxl > mxr || minn[mil] < maxx[mxr]))last = minn[mil++];
else last = maxx[mxl++];
}
ans += last;
}
cout << ans << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
solve();
}
Boxes
比较简单的高中数学算概率的问题吧，对于每一种我们只需要求一次hint就知道有多少个黑球多少个白球了。
比较全开和一次hint开的情况，求出最小的那个
#include<vector>
#include<string>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
using namespace std;
//#define _ 0
//return ~~(0^_^0)~~
int n;
const int maxn = 1e5 + 5;
long double a[maxn];
long double c;
void solve() {
cin >> n >> c;
long double a1, a2;
a1 = a2 = 0.0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a1 = a1 + 1.0 * a[i];
}
a2 = a2 + c;
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
a2 += a[i] * (1.0 - 1.0 / pow(2, n - i));
}
cout<<fixed<<setprecision(6)<<min(a1, a2);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
Double String
dp问题还是等补了dp来补吧（哎）
Holding Two
题意
要求我们构造一个n行m列的矩阵，其中要求每一行每一列每一条对角线上都不能有连续三个字符相同
题解
由题意我们可以想到一个简单的构造，讲0和1两个两个的排再一起，行和列都这样构造，那么一定不可能出现连续三个相同的情况
如3 3 就是
1 1 0
0 0 1
1 1 0
这样是不会出现连续三个相同的情况的；
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<string>a(n);
for (int i = 0; i < n; i++) {
int flag = 0;
if (i % 2 == 0) {
for (int j = 0; j < m; j += 2) {
flag++;
if (flag % 2 == 0)a[i] += "00";
else a[i] += "11";
}
}
else {
for (int j = 0; j < m; j += 2) {
flag++;
if (flag % 2 == 0)a[i] += "11";
else a[i] += "00";
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j];
}
cout << endl;
}
}
int main() {
solve();
}
Jewels
题意
题目的意思是求最小消耗的精力
在三维平面上有一些宝物，这些宝物会随时间以各自的v的速度往下掉，捡起这个宝物的代价是它和我们距离的平方
由此我们可以建立一个时间宝物的二部图，每个图的边权就是所需要的代价，找出它的最优匹配，最优匹配中所有权值的和就是我们要求的代价。
（嫖到板子了真开心）
#include<vector>
#include<string>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
//#define _ 0
//return ~~(0^_^0)~~
#define ll long long
const int N=407,NPOS=-1;
const ll INF=1ll<<60;
struct Matrix
{
int n;
ll a[N][N];
};
struct KuhnMunkres:Matrix
{
ll hl[N],hr[N],slk[N];
int fl[N],fr[N],vl[N],vr[N],pre[N],q[N],ql,qr;
int check(int i)
{
if(vl[i]=1,fl[i]!=NPOS)return vr[q[qr++]=fl[i]]=1;
while(i!=NPOS)swap(i,fr[fl[i]=pre[i]]);
return 0;
}
void bfs(int s)
{
fill(slk,slk+n,INF),fill(vl,vl+n,0),fill(vr,vr+n,0);
for(vr[q[ql=0]=s]=qr=1;;)
{
for(ll d; ql<qr;)
for(int i=0,j=q[ql++]; i<n; ++i)
if(!vl[i]&&slk[i]>=(d=hl[i]+hr[j]-a[i][j]))
if(pre[i]=j,d)slk[i]=d;
else if(!check(i))return;
ll d=INF;
for(int i=0; i<n; ++i)
if(!vl[i]&&d>slk[i])d=slk[i];
for(int i=0; i<n; ++i)
{
if(vl[i])hl[i]+=d;
else slk[i]-=d;
if(vr[i])hr[i]-=d;
}
for(int i=0; i<n; ++i)
if(!vl[i]&&!slk[i]&&!check(i))return;
}
}
void ask()
{
fill(fl,fl+n,NPOS),fill(fr,fr+n,NPOS),fill(hr,hr+n,0);
for(int i=0; i<n; ++i)hl[i]=*max_element(a[i],a[i]+n);
for(int j=0; j<n; ++j)bfs(j);
}
} km;
int n;
ll ans;
void solve() {
cin>>n;
for (int i=0;i<n;i++) {
int x,y,z,v;
cin>>x>>y>>z>>v;
ans+=x*x+y*y;
for (int j=0;j<n;j++) km.a[i][j]=(1ll<<50)-(ll)(z+v*j)*(z+v*j);
}
km.n=n;
km.ask();
for (int i=0;i<n;i++) ans+=(1ll<<50)-km.a[i][km.fl[i]];
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}