首页 > 其他分享 >暑假集训一

暑假集训一

时间：2022-08-17 22:24:18浏览次数：56  
标签：int read maxn kk 暑假 集训 dp define

暑假集训1

玩游戏

其实是是一个很水的题，只要从k开始向左向右找到最远能到的点就行，最后如果是1和n就YES否则就NO,前缀和判一下就行..就是吧左开右闭的左边界加个1变成左闭右闭,也算小寄巧吧，我写了200行，有点冗长，就不贴我的了

这里贺了lLiu的 
#include<bits/stdc++.h>
#define ll long long
#define rg register
#define rll rg ll
#define maxn 100001
using namespace std;
static inline ll read()
{
	rll f=0,x=0;rg char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
static inline void write(rll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);putchar(x%10|48);
}
ll t,n,k,l,r;
ll a[maxn],sum[maxn];
bool fl;
int main()
{
	// freopen("out.txt","w",stdout);
	t=read();
	while(t--)
	{
        memset(sum,0,sizeof(sum));
		n=read();k=read();read();
        for(rll i=2;i<=n;i++) a[i]=read();
        for(rll i=k-1;i;i--) sum[i]=sum[i+1]+a[i+1];
        for(rll i=k+1;i<=n;i++) sum[i]=sum[i-1]+a[i];
        r=k+1;fl=0;
        for(rll j=k;j;j--)
        {
            while(sum[j]+sum[r+1]<=0&&r<n) r++;
            while(sum[j]+sum[r]>0) r--;
            if(r<k) {fl=1;break;}
        }
		if((!fl)&&r==n) puts("Yes");
		else puts("No");
	}
	return 0;
}
whp 
#include <iostream>
using namespace std;
#define ll long long
inline ll in(){
    ll x = 0;
    bool f = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f ^= 1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    if(f) return -x;
    return x;
}
const int N = 1e5+1;
int T,n,m;
ll a[N];
ll sum;
ll resl,resr;
int posl,posr;
int l,r;
bool vis;
inline bool work(){
    l = m+1,r = m;
    sum = 0;
    while(1){
        resl = sum;
        posl = l;
        posr = r;
        vis = 0;
        while(posl > 2 && resl >= sum){
            if(resl + a[posl - 1] <= 0) resl += a[posl - 1],posl--;
            else break;
            if(resl < sum){
                sum = resl;
                l = posl;
                vis = 1;
            }
        }
        resr = sum;
        while(posr < n && resr >= sum){
            if(resr + a[posr + 1] <= 0) resr += a[posr+1],posr++;
            else break;
            if(resr < sum){
                sum = resr;
                r = posr;
                vis = 1;
            }
        }
        if(l == 2 && r == n) return 1; 
        if(!vis){
            if(posl == 2 && posr == n && resl + resr - sum <= 0) return 1;
            return 0;
        }
    }
    return 0;
}
int main(){
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    T = in();
    while(T--){
        n = in();
        m = in();
        for(int i = 1;i <= n;++i) a[i] = in();
        if(work()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

排列

这个题是一个很妙的dp了啊，先放一个题解的那个三维的思路的

又是1liu的,话说连图都是他的 
#include<bits/stdc++.h>
#define ll long long
#define rg register
#define rll rg ll
#define maxn 1001
using namespace std;
static inline ll read()
{
	rll f=0,x=0;rg char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
static inline void write(rll x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);putchar(x%10|48);
}
ll n,k,p,ans;
ll f[maxn][maxn][2];
ll c[maxn][maxn];
#define C(a,b) c[a][b]
// 用费马小求组合数会T且在模数非素数时会被卡.

int main()
{
	n=read();k=read();p=read();
	// jc[0]=1;for(rll i=1;i<maxn;i++) jc[i]=jc[i-1]*i%p;
	c[0][0]=1;for(rll i=1;i<=n;i++) { c[i][0]=1; for(rll j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%p; }
	if(k-1>=log2(n)) { puts("0"); return 0; }
	for(rll i=0;i<=k;i++) f[0][i][0]=f[0][i][1]=1;
	for(rll i=1;i<=n;i++)
		for(rll j=1;j<=k;j++)
			for(rll l=1;l<=i;l++)
			{
				f[i][j][0]=(f[i][j][0]+C(i-1,l-1)*f[l-1][j-1][1]%p*f[i-l][j][0]%p)%p;
				f[i][j][1]=(f[i][j][1]+C(i-1,l-1)*(f[l-1][j][1]*f[i-l][j-1][1]%p+f[l-1][j-1][1]*f[i-l][j][1]%p-f[l-1][j-1][1]*f[i-l][j-1][1]%p+p)%p)%p;
			}
	for(rll i=1;i<=n;i++) ans=(ans+C(n-1,i-1)*(f[i-1][k][0]*f[n-i][k][0]%p-f[i-1][k-1][0]*f[n-i][k-1][0]%p+p)%p)%p;
	write(ans);
	return 0;
}

然后是我的四维dp

设\(dp[i][j][1 / 0][1 / 0]\)表示长度为i的区间操作j次后只剩一个
(但存的是从操作一次到操作j次的前缀和,所以理解成至多操作j次也可以->即前缀和优化，否则会T掉)第一个\(1 / 0\)表示左边界外是否有最大值(相对于当前区间来说，即大于区间内所有数),后一个\(1 / 0\)同理右边界，注意是区间的边界

\(然后考虑转移\)

首先对于一个大区间,它可以被区间里的最大值分为两个互不干扰的小区间，所以一个大区间的方案数是由两个小区间的方案数乘组合数来得出的(因为是从大区间随意选数进入第一个区间，剩下的进入第二个区间)

但是因为直接\(C\)会\(T\)所以用杨辉三角求\(C\)
(小题b事还挺多)

  • 最大值在\(k\)

  • 第一种对于\(0, 0\)的情况

    • 因为两边都没有最大值,所以最大值在内部，就可以从相同j的左\([0][1]\)区间和右\([1][0]\)区间转移过来(最大值独立出来，最后左边的小大和右边的小大和最大消掉，我定义是消到剩一个,但我求的是方案不是步数，所以等效,就是自己的两边都消完了,那自己就确定了),组合意义就是从\(i - 1\)个数中任意选\(k - 1\)个放在左边
      \(dp[i][j][0][0]\) \(=\) \(\sum_{k=1}^i\) \(dp[k - 1][j][0][1]\) * \(dp[i-k][j][1][0]\) * \(C_{i-1}^{k-1}\)

      (\(k - 1\) 和 \(i - k\) 加起来就是 \(i - 1\), 去掉最大值的区间长度)

  • 第二种对于\(1, 0\)的情况

    • 如果我们想让它在j次内消完, 那么区间内的最大值在\(j - 1\)次时应该与左边界相遇(因为比他大的在左边)，这样第\(j\)次才能消了它，所以，对左区间而言，两侧都有最值(我i区间内的左区间而非i外的左区间)，右区间的左边界外有最值，所以由\(j - 1\)的左\([1][1]\)区间和\(j\)的右\([1][0]\)区间转移过来
      \(dp[i][j][1][0]=\sum_{k=1}^i dp[k - 1][j - 1][1][1] * dp[i - k][j][1][0] * C_{i-1}^{k-1}\)

  • 第三种对于\(0, 1\)的情况

    • 同理第二种
      \(dp[i][j][0][1] = \sum_{k = 1} ^ i dp[k - 1][j][0][1] * dp[i - k][j - 1][1][1]*C_{i-1}^{k-1}\)

  • 第四种对于\(1, 1\)的情况

    • 因为左右两边都有最值，既可以和左边的消掉，又可以和右边的消除，所以那么只需要任意一边\(j−1\)轮内消完即可, k靠左或者靠右都行，所以先由两边都是\(j\)转移过来，最后容斥一下,把两边恰好同时选j的情况减去即可
      $ dp[i][j][1][1]=\sum_{k=1}^i (dp[k - 1][j][1][1] * dp[i - k][j][1][1]-(dp[k - 1][j][1][1]-dp[k - 1][j - 1][1][1]) * (dp[i - k][j][1][1] - dp[i - k][j - 1][1][1])) * C_{i-1}^{k-1}$

  • 因为是前缀和，所以最后答案是\(dp[n][k][0][0] - dp[n][k - 1][0][0]\)

我的 
#include <bits/stdc++.h>
#define fuc(x, y) inline x y
#define frein(x) dpreopen(#x ".in", "r", stdin)
#define freout(x) dpreopen(#x ".out", "w", stdout)
#define Re register int
#define mes(x) memset(x, 0, sizeodp (x))
#define LL long long
#define LD double
#define ki putchar('\n')
#define fk putchar(' ')
#define fr(x, y, z) for(Re x = y; x <= z; x ++)
#define fp(x, y, z) for(Re x = y; x >= z; x --)
#define WMX aiaiaiaiai~~~~~~~~~~~
using namespace std;

namespace kkiritokkazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template <typename T> fuc(void, write) (T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10);putchar(x % 10 | '0');
    }

}

using namespace kkiritokkazuto;
const int maxn = 1e3 + 100;
//这个相邻是双向的...害的我模了半天...... [5, 4]中4也算和5相邻
LL dp[maxn][100][2][2];//先左后右是否靠墙，0靠墙
//区间长度i 操作j次 -> 从操作一次到操作j次的前缀和
LL n, k, p;
LL C[maxn][maxn];
fuc(void, init)(LL x){
    fr(i, 0, x + 1){
        dp[0][i][0][0] = dp[0][i][1][1] = dp[0][i][0][1] = dp[0][i][1][0] = 1;
    }
    fr(i, 0, n){
        C[i][0] = 1;
        //杨辉三角组合数？
        fr(j, 1, i){
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
        }
    }
}

signed main(){
    n = read();
    k = read();
    p = read();
    init(k);
    fr(i, 1, n){
        fr(kk, 1, k + 1){
            fr(j, 1, i){
                dp[i][kk][0][0] += ((dp[j - 1][kk][0][1] * dp[i - j][kk][1][0]) % p * C[i - 1][j - 1]) % p;
                dp[i][kk][0][1] += ((dp[j - 1][kk][0][1] * dp[i - j][kk - 1][1][1]) % p * C[i - 1][j - 1]) % p;
                dp[i][kk][1][0] += ((dp[j - 1][kk - 1][1][1] * dp[i - j][kk][1][0]) % p * C[i - 1][j - 1]) % p;
                dp[i][kk][1][1] += (((dp[j - 1][kk][1][1] * dp[i - j][kk][1][1]) - (dp[j - 1][kk][1][1] - dp[j - 1][kk - 1][1][1]) * (dp[i - j][kk][1][1] - dp[i - j][kk - 1][1][1])) % p * C[i - 1][j - 1]) % p;
                dp[i][kk][0][0] %= p;
                dp[i][kk][0][1] %= p;
                dp[i][kk][1][0] %= p;
                dp[i][kk][1][1] %= p;

            }
        }
    }
    write(((dp[n][k][0][0] - dp[n][k - 1][0][0]) % p + p) % p);//前缀和
}
/*
2 1 998244353
3 1 998244353
4 1 998244353
5 1 998244353
6 1 998244353
7 1 998244353
8 1 998244353
9 1 998244353
10 1 998244353
*/

最短路

先来个毒瘤的,把所有点删便就过了那种

here 
#include <bits/stdc++.h>
#define fuc(x, y) inline x y
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define Re register int
#define mes(x) memset(x, 0, sizeof (x))
#define LL long long
#define LD double
#define ki putchar('\n')
#define fk putchar(' ')
#define fr(x, y, z) for(Re x = y; x <= z; x ++)
#define fp(x, y, z) for(Re x = y; x >= z; x --)
#define WMX aiaiaiaiai~~~~~~~~~~~
using namespace std;

namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template <typename T> fuc(void, write) (T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10);putchar(x % 10 | '0');
    }

}

using namespace kiritokazuto;
const int maxn = 5000, Inf = 2147483647;
deque <int> q1, q2;
int vis1[maxn], vis2[maxn];
random_device seed;
mt19937 rrand(seed());
struct Node{
    int to, next;
}wmx[maxn << 2];

int head[maxn], len = 0;
LL dis1[maxn], dis2[maxn];
fuc(void, Qian)(int from, int to){
    wmx[++len].to = to;
    wmx[len].next = head[from];
    head[from] = len;
}
int val[maxn];
int n, m;
int cut[maxn];
int did1[maxn];
int did2[maxn];
int pre[maxn];
int tmpval[maxn];
LL ans = 0x7fffffffffffffff;
fuc(LL, minn)(LL x, LL y) {return (x > y) ? y : x;}
fuc(void, Spfa1)(int x) {
    memset(dis1, 22, sizeof(dis1));
  //  write(dis1[1]);
   // ki;
    fr(i, 1, n)vis1[i] = 0;
    vis1[x] = 1;
    q1.push_back(x);
    dis1[x] = 0;
    while(!q1.empty()) {
        int top = q1.front();
        q1.pop_front();
        vis1[top] = 0;
        for(Re i = head[top]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(cut[to])continue;
            if(dis1[to] > dis1[top] + val[to]) {
                dis1[to] = dis1[top] + val[to];
                pre[to] = top;
                if(vis1[to])continue;
                // q1.push_back(to);
                if(rrand() & 1)q1.push_back(to);
                else q1.push_front(to);
                vis1[to] = 1;
            }
        }
    }
}
fuc(void, Spfa2)(int x) {
    memset(dis2, 22, sizeof(dis2));
    fr(i, 1, n)vis2[i] = 0;
    vis2[x] = 1;
    q2.push_back(x);
    dis2[x] = 0;
    while(!q2.empty()) {
        int top = q2.front();
        q2.pop_front();
        vis2[top] = 0;
        for(Re i = head[top]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(cut[to])continue;
            if(dis2[to] > dis2[top] + val[to]) {
                dis2[to] = dis2[top] + val[to];
                if(vis2[to])continue;
                // q2.push_back(to);
                if(rrand() & 1)q2.push_back(to);
                else q2.push_front(to);
                vis2[to] = 1;
            }
        }
    }
}
signed main(){
    n = read();
    m = read();
    fr(i ,1, n)tmpval[i] = val[i] = read();
    fr(i, 1, m) {
        int x = read(), y = read();
        Qian(x, y);
    }
    Spfa1(1);
    if(dis1[n] >= 1591483802437686806) {
        printf("-1");
        return 0;
    }
    int ttmp = n;
    while(pre[ttmp]) {
        val[ttmp] = 0;
        ttmp = pre[ttmp];
    } 
    Spfa2(n);
    ttmp = n;
    while(pre[ttmp]) {
        val[ttmp] = tmpval[ttmp];
        ttmp = pre[ttmp];
    }

    if(dis2[1] >= 1591483802437686806) {
        printf("-1");
        return 0;
    }
    ans = minn(dis1[n] + dis2[1], ans);
   // write(ans);
    fr(i, 2, n - 1) {
        cut[i] = 1;
        Spfa1(1); 
        int tmp = n;
        while(pre[tmp]) {
            val[tmp] = 0;
            tmp = pre[tmp];
        } 
        Spfa2(n);
        tmp = n;
        while(pre[tmp]) {
            val[tmp] = tmpval[tmp];
            tmp = pre[tmp];
        }
        ans = minn(dis1[n] + dis2[1], ans);
        cut[i] = 0;
       // printf("KKKKKKKKKKK\n");
    }
    //printf("KKKKKKKKKKK<");
    fr(i, 2, n - 1) {
        cut[i] = 1;
        Spfa1(n);
        int tmp = 1;
        pre[n] = 0;
        while(pre[tmp]) {
          // printf("sb!@\n");
            val[tmp] = 0;
            tmp = pre[tmp];
        }
        Spfa2(1);
        tmp = 1;
        while(pre[tmp]) {
            val[tmp] = tmpval[tmp];
            tmp = pre[tmp];
        }
        ans = minn(dis1[1] + dis2[n], ans);
        cut[i] = 0;
        // printf("KKKKKKKKKKK\n");
    }
    
    if(ans == 0x7fffffffffffffff) {
        printf("-1");
    }else {
        write(ans);
    }
    return 0;
}
  • 然后开始正解\(~~神tm二维dij~~\)
    • 就是建个正图再建个反图，两个点同时从一出发跑\(dij\)
    • \(dis[i][j]\)表示从两个点从正图到点i与从反图到点j的距离之和, 答案显然为\(dis[n][n]\)
    • 再用三维bool或者bitset维护一下路径上哪个门票买了就行(其正确性是因为我维护的是当前状态的bool当前状态不会影响其他并列状态eg : \(bool[i][j][k]\)表示当前到\(i\)和到\(j\)时\(k\)付没付过钱)
因为没有写正解，所以贺了棍哥的 
//趁着没被hack赶紧换成正解
//正解可以从两个状态同时跑dj，都到n就停 
#include <bits/stdc++.h>
#define endl putchar('\n')
using namespace std;
const int M = 1000;
const int inf = 2147483647;
const int Mod = 998244353;
typedef long long ll;
inline ll read(){
	ll x=0,f=0;char c=getchar();
	while(!isdigit(c)){
		if(c=='-') f=1;
		c=getchar();
	}
	do{
		x=(x<<3)+(x<<1)+(c^48);
	}while(isdigit(c=getchar()));
	return f?-x:x;
}
inline void print(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);putchar(x%10^48);
}
struct Node{
	int x,y,dis;
	Node(){};
	Node(int a,int b,int c){
		x=a;y=b;dis=c;
	}
	bool operator < (const Node &a)const{
		return dis > a.dis; 
	}
};
priority_queue<Node> q;
vector<int> pos[M],neg[M];//正图和反图
int val[M],dis[M][M]; 
bool vis[M][M];
bitset<M> Free[M][M];//记录当前状态下某个点有没有被跑过 
int n,m;
void dij(int st){
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=inf;
	dis[st][st]=val[st];
	Free[st][st][st]=1;
	q.push(Node(st,st,dis[st][st]));
	while(!q.empty()){
		int x=q.top().x,y=q.top().y,w=q.top().dis;
		q.pop();
		if(!vis[x][y]){
			vis[x][y]=1;
			for(int i=0;i<pos[x].size();i++){
				int v=pos[x][i];
				int add=w+(Free[x][y][v]?0:val[v]);
				if(dis[v][y]>add){
					dis[v][y]=add;
					Free[v][y]=Free[x][y];
					Free[v][y][v]=1;
					q.push(Node(v,y,dis[v][y]));
				}
			}
			for(int i=0;i<neg[y].size();i++){
				int v=neg[y][i];
				int add=w+(Free[x][y][v]?0:val[v]);
				if(dis[x][v]>add){
					dis[x][v]=add;
					Free[x][v]=Free[x][y];
					Free[x][v][v]=1;
					q.push(Node(x,v,dis[x][v]));
				}
			}
		}
	}
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++) val[i]=read();
	for(int i=1;i<=m;i++){
		int rd=read(),fs=read();
		pos[rd].push_back(fs);
		neg[fs].push_back(rd);
	}
	dij(1);
	print((dis[n][n]==inf)?-1:dis[n][n]);
	return 0;
}

矩形

先来我自创的随机化 \(n^{2}\)~暴力都能过...~~~

当然这是个阴间玩意，不要轻易学 
#include <bits/stdc++.h>
#define fuc(x, y) inline x y
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define Re register int
#define mes(x) memset(x, 0, sizeof (x))
#define LL long long
#define LD double
#define ki putchar('\n')
#define fk putchar(' ')
#define fr(x, y, z) for(Re x = y; x <= z; x ++)
#define fp(x, y, z) for(Re x = y; x >= z; x --)
#define WMX aiaiaiaiai~~~~~~~~~~~
using namespace std;

namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template <typename T> fuc(void, write) (T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10);putchar(x % 10 | '0');
    }

}

using namespace kiritokazuto;
const int maxn = 1e5 + 100;
int fa[maxn];
vector <int> wmx[maxn];
int cnt;
struct Node{
    int l, r, h, d;
}crt[maxn];
fuc(int, maxx)(int x, int y) {return(x > y) ? x : y;}
fuc(int, minn)(int x,int y) {return (x > y) ? y : x;}
fuc(bool, check)(int x, int y){
    int lmax = maxx(crt[x].l, crt[y].l);
    int rmin = minn(crt[x].r, crt[y].r);
    // if (x == 4){
    //     printf("This is y = %d\n", y);
    //     printf("crt[%d].l = %d \n crt[%d].r = %d\n crt[%d].l = %d \n crt[%d].r = %d\n", x, crt[x].l, x, crt[x].r, y, crt[y].l, y, crt[y].r);
    //     ki;
    // }
    if (lmax <= rmin){
        int hmin = minn(crt[x].h, crt[y].h);
        int dmax = maxx(crt[x].d, crt[y].d);
        if (dmax <= hmin)return 1;
        else return 0;
    }
    return 0;
}
fuc(int, find)(int x){ return (x == fa[x]) ? x : fa[x] = find(fa[x]); }
fuc(void, merge)(int x, int y){
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) fa[fx] = fy;
}
int n;

int vis[maxn];
bool cmp(Node A, Node B) {
    if(A.l == B.l) {
        if(A.d == B.d) {
            if(A.r == B.r) {
                return A.h < B.h;
            }else {
                return A.r < B.r;
            }
        }else {
            return A.d < B.d;
        }
    }else {
        return A.l < B.l;
    }
}
signed main(){
    n = read();
    fr(i, 1, n) fa[i] = i;
    fr(i, 1, n){
        crt[i].l = read();
        crt[i].d = read();
        crt[i].r = read();
        crt[i].h = read();
        // fp(j, i - 1, 1){
        //     if (check(i, j)){
        //         // wmx[i].push_back(j);
        //         // wmx[j].push_back(i);
        //         // printf("here is crt %d %d\n", i, j);
        //         merge(i, j);
        //     }
        // }
    }
    int ans = 0;
    sort(crt + 1, crt + n + 1, cmp);
    fr(i, 1, n) {
        int cnt = 0;
        for(Re j = 1; j <= n; j ++) {
            if(cnt == 20)break;
            if(i!=j&&check(i, j)) {
                fa[find(i)] = find(j);
                cnt++;
            }
        }
    }
    fr(i, 1, n){
        if (!vis[find(i)]){
            ans++;
            vis[find(i)] = 1;
        }
    }
    write(ans);
    return 0;
}
  • 正解没打，放一个crs的CDQ和Kaguya的分块
crs 


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#define lid(a) (a<<1)
#define rid(a) (a<<1|1)
using namespace std;
const int N=100000;
inline int read()
{
    int x=0,f=1; char c;
    while(!isdigit(c=getchar())) if(c=='-') f=-1;
    do x=(x<<1)+(x<<3)+(c^48); while(isdigit(c=getchar()));
    return x*f;
}
int H,maxy,tot,ans;
int c[N],fa[N];
struct Mar{int lx,rx,ly,ry,lim;}mar[N],proc[N];
struct Mac{int lx,rx,ly,ry,sig;}mac[N];
set<Mac>sel[N<<2],cov[N<<2],con;
inline bool operator <(const Mac A,const Mac B){ return (A.lx==B.lx)?(A.rx<B.rx):(A.lx<B.lx); }
inline bool cmpo(const Mar A,const Mar B){ return (A.lx==B.lx)?((A.rx==B.rx)?(A.ly<=B.ly):(A.rx<=B.rx)):(A.lx<=B.lx); }
inline bool cmpt(const Mar A,const Mar B){ return (A.rx==B.rx)?(A.ly<=B.ly):(A.rx<=B.rx); }
int lowbit(int x){ return x&(-x); }
void update(int x,int val){ while(x<=maxy){ c[x]=max(c[x],val); x+=lowbit(x); } }
void init(int x,int val){ while(x<=maxy){ c[x]=min(c[x],val); x+=lowbit(x); } }
int check(int x){ int ans=0; while(x){ ans=max(ans,c[x]); x-=lowbit(x); } return ans; }
void Try_cdq(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	Try_cdq(l,mid); Try_cdq(mid+1,r);
	for(int i=r,j=mid;i>=mid+1;i--)
	{
		while(j>=l&&mar[i].rx<=mar[j].rx) update(mar[j].ly,mar[j].ry),j--;
		mar[i].lim=max(mar[i].lim,check(mar[i].ly-1));
		if(i==mid+1) for(int k=mid;k>j;k--) init(mar[k].ly,0);
	}
	merge(mar+l,mar+mid+1,mar+mid+1,mar+r+1,proc+l,cmpt);
	memcpy(mar+l,proc+l,sizeof(Mar)*(r-l+1));
}
int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; }
void merge(int x,int y){ int a=find(x),b=find(y); if(a==b) return; fa[b]=a; }
set<Mac> & Together(set<Mac>&A,set<Mac>&B) 
{ 
	bool P=0; 
	if(A.size()<B.size()) swap(A,B),P=1; 
	con=A; 
	A.insert(B.begin(),B.end());
	swap(con,A); 
	if(P) swap(A,B);
	return con;
}
void pushup(int nn)
{
	swap(sel[nn],Together(sel[lid(nn)],sel[rid(nn)]));
}
void pushdown(int nn)
{
	if(cov[nn].size())
	{
	    swap(cov[lid(nn)],Together(cov[lid(nn)],cov[nn]));
		swap(cov[rid(nn)],Together(cov[rid(nn)],cov[nn]));
		swap(sel[lid(nn)],Together(sel[lid(nn)],cov[nn]));
		swap(sel[rid(nn)],Together(sel[rid(nn)],cov[nn]));
		cov[nn].clear();
	}
}
void update(int nn,int l,int r,int F,int T,int sig)
{
	if(l==F&&r==T) return (void)(sel[nn].insert(mac[sig]),cov[nn].insert(mac[sig]));
	int mid=(l+r)>>1;
	pushdown(nn);
	if(T<=mid) update(lid(nn),l,mid,F,T,sig);
	else if(F>mid) update(rid(nn),mid+1,r,F,T,sig);
	else update(lid(nn),l,mid,F,mid,sig),update(rid(nn),mid+1,r,mid+1,T,sig);
	pushup(nn);
}
void Connect(int nn,int l,int r,int F,int T,int L,int R,int sig)
{
	if(l==F&&r==T)
	{
		for(auto it :sel[nn])
		{
			if(it.rx<L) continue;
			if(it.lx>R) break;
			merge(sig,it.sig);
		}
		return;
	}
	pushdown(nn);
	int mid=(l+r)>>1;
	if(T<=mid) Connect(lid(nn),l,mid,F,T,L,R,sig);
	else if(F>mid) Connect(rid(nn),mid+1,r,F,T,L,R,sig);
	else Connect(lid(nn),l,mid,F,mid,L,R,sig),Connect(rid(nn),mid+1,r,mid+1,T,L,R,sig);
}
int main()
{
	H=read();
	for(int i=1;i<=H;i++)
	{
		int lx=read(),ly=read(),rx=read(),ry=read();
		mar[i]=(Mar){lx,rx,ly,ry,ry};
		maxy=max(maxy,ry);
	}
	sort(mar+1,mar+H+1,cmpo);
	Try_cdq(1,H);
	for(int i=1;i<=H;i++)
	{
		if(mar[i].lim!=mar[i].ry) continue;
		++tot;
		mac[tot]=(Mac){mar[i].lx,mar[i].rx,mar[i].ly,mar[i].ry,tot};
		fa[tot]=tot;
		update(1,1,maxy,mac[tot].ly,mac[tot].ry,tot);
	}
	for(int i=1;i<=tot;i++) Connect(1,1,maxy,mac[i].ly,mac[i].ry,mac[i].lx,mac[i].rx,i);
	for(int i=1;i<=tot;i++) if(find(i)==i) ans++;
	printf("%d\n",ans);
	// printf("\n%d",tot);
	return 0;
}
Kaguya 

//淦，早苗线+并查集。以前没有打过。awsl
//什么花里胡哨的，直接一个暴力模拟就够了（大悲）
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#define sqsz 10001
#define sz 5000001
struct sot
{
	char kid;
	int x, st, ed;
};
struct sot dld[sz << 1];
int n, now, mx, sq;
int fsl[sz], num[sz], tree[sz], own[sz], laz[sqsz], st[sqsz], ed[sqsz], sum[sqsz];
bool cmp(const sot&, const sot&);
int read();
int zip(int);
void fix(int);
void code(int, int);
void force(int, int);
int main()
{
	int x, y, w, c;
	n = read();
	for (int i = 1; i <= n; ++i)
	{
		x = read(); y = read();
		w = read(); c = read();
		if (mx < c)
			mx = c;
		++now;
		dld[now].kid = 0;
		dld[now].x = x;
		dld[now].st = y;
		dld[now].ed = c;
		++now;
		dld[now].kid = 1;
		dld[now].x = w;
		dld[now].st = y;
		dld[now].ed = c;
	}
	sq = sqrt(mx);
	for (int i = 1, j = 1; i <= mx; ++j)
	{
		st[j] = i;
		ed[j] = i + sq;
		if (ed[j] > mx)
			ed[j] = mx;
		while (i <= ed[j])
		{
			own[i] = j;
			++i;
		}
	}
	w = now;
	std::sort(dld + 1, dld + 1 + w, cmp);
	now = x = 0;
	for (int i = 1; i <= w; ++i)
		fix(i);
	for (int i = 1; i <= now; ++i)
		tree[i] = 0;
	for (int i = 1; i <= now; ++i)
	{
		fsl[i] = zip(fsl[i]);
		if (!tree[fsl[i]])
		{
			++x;
			tree[fsl[i]] = 1;
		}
	}
	printf ("%d", x);
	return 0;
}

bool cmp(const sot &a, const sot &b)
{
	if (a.x == b.x)
		return a.kid < b.kid;
	return a.x < b.x;
}

int read()
{
	int x = 0;
	char c = 0;
	while (!isdigit(c = getchar()));
	do {
		x = (x << 3) + (x << 1) + (c & 15);
	}while (isdigit(c = getchar()));
	return x;
}

int zip(int a)
{
	int tmp, sav = a;
	while (a != fsl[a])
		a = fsl[a];
	while (sav != a)
	{
		tmp = fsl[sav];
		fsl[sav] = a;
		sav = tmp;
	}
	return a;
}

void fix(int a)
{
	int x = dld[a].st, y = dld[a].ed;
	if (dld[a].kid == 1)
	{
		if (own[x] == own[y])
		{
			if (x == st[own[x]] && y == ed[own[x]])
				--sum[own[x]];
			else
				for (int i = x; i <= y; ++i)
					--tree[i];
		}else
		{
			if (x == st[own[x]])
				x = own[x];
			else
			{
				for (int i = x; i <= ed[own[x]]; ++i)
					--tree[i];
				x = own[x] + 1;
			}
			if (y == ed[own[y]])
				y = own[y];
			else
			{
				for (int i = st[own[y]]; i <= y; ++i)
					--tree[i];
				y = own[y] - 1;
			}
			while (x <= y)
			{
				--sum[x];
				++x;
			}
		}
	}else
	{
		++now;
		fsl[now] = now;
		if (own[x] == own[y])
		{
			if (x == st[own[x]] && y == ed[own[x]])
			{
				if (sum[own[x]])
				{
					fsl[zip(laz[own[x]])] = now;
				}else
					force(x, y);
				laz[own[x]] = now;
				++sum[own[x]];
			}else
			{
				if (sum[own[x]])
				{
					fsl[zip(laz[own[x]])] = now;
					laz[own[x]] = now;
					for (int i = x; i <= y; ++i)
						++tree[i];
				}else
					code(x, y);
			}
		}else
		{
			if (x == st[own[x]])
				x = own[x];
			else
			{
				if (sum[own[x]])
				{
					fsl[zip(laz[own[x]])] = now;
					laz[own[x]] = now;
					for (int i = x; i <= ed[own[x]]; ++i)
						++tree[i];
				}else
					code(x, ed[own[x]]);
				x = own[x] + 1;
			}
			if (y == ed[own[y]])
				y = own[y];
			else
			{
				if (sum[own[y]])
				{
					fsl[zip(laz[own[y]])] = now;
					laz[own[y]] = now;
					for (int i = st[own[y]]; i <= y; ++i)
						++tree[i];
				}else
					code(st[own[y]], y);
				y = own[y] - 1;
			}
			while (x <= y)
			{
				if (sum[x])
					fsl[zip(laz[x])] = now;
				else
					force(st[x], ed[x]);
				laz[x] = now;
				++sum[x];
				++x;
			}
		}
	}
}

void code(int a, int b)
{
	for (int i = a; i <= b; ++i)
	{
		if (tree[i])
			fsl[zip(num[i])] = now;
		num[i] = now;
		++tree[i];
	}
}

void force(int a, int b)
{
	for (int i = a; i <= b; ++i)
		if (tree[i])
		{
			fsl[zip(num[i])] = now;
			num[i] = now;
		}
}

标签：int,read,maxn,kk,暑假,集训,dp,define
From： https://www.cnblogs.com/kiritokazuto/p/16596976.html

相关文章

  • 雅礼NOIP2018集训 day3 w
    雅礼NOIP2018集训day3w题面有一棵n个节点的树，每条边长度为1，颜色为黑或白。可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。对于某些边，要求在操作结......
  • [游记]暑假集训5-2022.8.17
    今天的题目都比较有思维量，嗯A.星际旅行考虑一下去掉那两条有向边，就是一个典型的欧拉回路然后问的就是能够生成的欧拉回路的个数考虑每次删掉两条边，有三种删除方法：$\q......
  • 暑期集训4
    rank29mark150题纲：T1：赛时全员AC，其他的应该不用说什么了T2：图论，竞赛图统计强连通分量（位运算的应用）T3：计数类DPT4：线段树维护dfs序-->树剖-->染色T2:定义竞赛图，任意两点......
  • [游记]暑假集训4-2022.8.16
    今天还行？不过挂了$85$分A.打地鼠场切签到题  #include<cstdio>#include<cstring>#include<string>#include<queue>#defineintlonglong#defineWRWin......
  • P5931 [清华集训2015]灯泡——三分法
    一道不错的题，只是重构数据后精度太奇怪了，必须打表才能过题目分析根据题意我们可以抽象出一个直角梯形，并设人到墙壁的距离为\(x\)，设影子在墙上的高度为\(y\)如果没有在......
  • [游记]暑假集训3-2022.8.15
    Rank2，终于没有$\cdots\cdots$不，挂分少了A.数列显然一眼先扩欧发现如果$n$个数中有一个不能被$\gcd(a,b)$整除就无解那么对于每个$x_i$我们要解$ap+bq=x_i$中......
  • 暑假集训3
    去年暑假打过一次，但是当时太菜，今天看到之前写过，好奇多少分，考后交了一发，发现自己是真的菜然后，就算开了个坑吧，四道题。。。A.数列\(exgcd\)板子然后，\(exgcd\)咋用来着？......
  • 2022牛客暑假第七场C、F、J、K
    C-ConstructiveProblemsNeverDie_"蔚来杯"2022牛客暑期多校训练营7(nowcoder.com)容易知道，只要A中的数不是全部相同，就一定有解。我们思考如何构造：如果A中的数是一......
  • hfyz 集训随笔
    大概在中考分数刚出来的时候一中就通知要搞集训了正好我有zr集训，就打算鸽了（大概在集训开始前被拉倒了群里然后发现有wty和hzy来，有点想去了最后还是决定zr比赛后来在集......
  • P2619 [国家集训队]Tree I（K 度限制生成树 二分）
    P2619[国家集训队]TreeI一张\(n\)个点\(m\)条边的带权无向联通图，每条边是黑色或白色。求一棵最小权的恰好有\(need\)条白色边的生成树，题目保证有解。\(n\le5\t......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99