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();
}