首页 > 其他分享 >暑假集训四[打地鼠, 竞赛图, 糖果, 树]

暑假集训四[打地鼠, 竞赛图, 糖果, 树]

时间：2022-08-18 07:12:13浏览次数：69  
标签：fr putchar int 地鼠 maxn 暑假 集训 dp define

暑假集训4

打地鼠

这个题是个人也会吧？二维前缀和暴力碾压硬扫就行了，就是注意好边界，别爆就行

here 
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD long double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#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 frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_pair(x, y)
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 = 2e3 + 10, Mod = 1e9 + 7;
const int Inf = 2147483647;


/*
她在夜里穿过我梦中的湖，在它的岸边，我看见过诸神漫步，而从湖心深处，我的魔法城堡升起。
她踩着梦幻阶梯，闯入我的不夜城
*/

int n, k;

//二维前缀和直接暴力
int sum[maxn][maxn];
char s[maxn];
signed main(){
    n = read();
    k = read();
    fr(i, 1, n){
        scanf("%s", s + 1);
        fr(j, 1, n){
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + s[j] - '0';
        }
    }
    // fr(i, 1, n){
    //     fr(j, 1, n){
    //         printf("sum[%d][%d] = %d\n", i, j, sum[i][j]);
    //     }
    // }
    int ans = 0;
    fr(i, k, n){
        fr(j, k, n){
            ans = max(ans, sum[i][j] - sum[i][j - k] - sum[i - k][j] + sum[i - k][j - k]);
            // printf("i = [%d] j = [%d] i - k = [%d] j - k = [%d]\n", i, j, i - k, j - k);
        }
    }
    write(ans);
    return 0;

}

竞赛图

这个题我现在可以说是理解的透透的了

  • 首先说暴力分
    • \(40pts\)暴力枚举子集，然后判联通就行
    • \(60pts\)还是枚举子集，但是加一个优化，每当找到一个强连通子图后，去枚举其他的点，看能否构成新的连通图，标记一下
      (\(60pts\)的我没写,放个棍哥的)
Touch 
#include <bits/stdc++.h>
#define endl putchar('\n')
using namespace std;
const int M = 50;
const int inf = 2147483647;
const int Mod = 998244353;
typedef long long ll;
inline int read(){
	int 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);
}
bool vis[M],ins[M];
int in[M][M],out[M][M];
int n,s[M],top;
void dfs(int x){
	vis[x]=1;
	for(int i=1;i<=out[x][0];i++){
		int v=out[x][i];
		if(vis[v]) continue;
		if(!ins[v]) continue;
		dfs(v);
	}
}
int cnt;
bool check(){
	cnt++;
	for(int i=1;i<=n;i++){
		ins[i]=0;
	}
	for(int i=1;i<=top;i++){
		ins[s[i]]=1;
	}
	for(int i=1;i<=top;i++){
		for(int j=1;j<=n;j++) vis[j]=0;
		dfs(s[i]);
		for(int j=1;j<=top;j++){
			if(!vis[s[j]]) return 0;
		}
	}
	return 1;
}
int dp[(1<<24)+10];
void work(){
	int ans=0;
	n=read();
	int maxn=(1<<n)-1;
	for(int i=0;i<=maxn;i++) dp[i]=0;
	for(int i=1;i<=n;i++){
		in[i][0]=out[i][0]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x=read();
			if(x==1){
				in[j][++in[j][0]]=i;
				out[i][++out[i][0]]=j;
			}
		}
	}
	dp[0]=1;
	for(int i=0;i<n;i++){
		dp[(1<<i)]=1;
	}
	for(int i=1;i<=maxn;i++){
		if(dp[i]){//已经是强连通分量了 
			ans++;
			for(int j=1;j<=n;j++){
				if((i&(1<<(j-1)))) continue;//已经在里面了
				bool flag=0;
				for(int k=1;k<=out[j][0];k++){
					int v=out[j][k];
					if((i&(1<<(v-1)))){
						flag=1;break;
					}
				}
				if(flag){
					flag=0;
					for(int k=1;k<=in[j][0];k++){
						int v=in[j][k];
						if((i&(1<<(v-1)))){
							flag=1;break;
						}
					}
					if(flag){//组成新的连通分量 
						dp[(i|(1<<(j-1)))]=1;
					}
				} 
			}
		}
		else{
			if(log2(i)==2) continue;//两个肯定不行 
			top=0;
			for(int j=1;j<=n;j++){
				if((i&(1<<(j-1)))) s[++top]=j;
			}
			if(check()){
				dp[i]=1;
				ans++;
				for(int j=1;j<=n;j++){
					if((i&(1<<(j-1)))) continue;//已经在里面了
					bool flag=0;
					for(int k=1;k<=out[j][0];k++){
						int v=out[j][k];
						if((i&(1<<(v-1)))){
							flag=1;break;
						}
					}
					if(flag){
						flag=0;
						for(int k=1;k<=in[j][0];k++){
							int v=in[j][k];
							if((i&(1<<(v-1)))){
								flag=1;break;
							}
						}
						if(flag){//组成新的连通分量 
							dp[(i|(1<<(j-1)))]=1;
						}
					} 
				}
			}
		}
	}
	ans++;
	print(ans);endl;
//	printf(" dfs进行了%d次\n",cnt);
//	cnt=0;
}
signed main(){
//	freopen("a.in","r",stdin);
//	double st=clock();
	int t=read();
	while(t--){
		work();
	}
//	double ed=clock();
//	printf("%.0lfms",ed-st);
	return 0;
}

  • 然后来说我们心心念念的正解，简洁有力，就是难想

    • 首先贴一下题解
    • 对于这个方法三，先纠正一个地方，下边是设其中有的点的出边集合的交的点集为\(T\)
    • 然后我们来顺一下思路，我们用已知的强连通分量来处理出非强连通分量，最后统计答案，好像说了句废话
    • 算了，先上代码，对着代码讲来的快
Touch 
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD long double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#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 frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_pair(x, y)
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 = 2e7 + 10, Mod = 1e9 + 7;
const int Inf = 2147483647;
/*
她在夜里穿过我梦中的湖，在它的岸边，我看见过诸神漫步，而从湖心深处，我的魔法城堡升起。
她踩着梦幻阶梯，闯入我的不夜城
*/
int t;
//虽然邻接矩阵能存，但写Tarjan还是邻接表好点
//tnnd不写Tarjan了,这直接一坨了
fuc(LL, lowbit)(LL x){ return x & (-x); }

int n;
int ans;
LL fg[maxn];
LL codi[maxn];
signed  main(){
    t = read();
    while (t--){
        mes(codi, 0);
        mes(fg, 0);
        n = read();
        LL Maxs = 1 << n;
        ans = Maxs;
        fr(i, 1, n)
            fr(j, 1, n){
            int x = read();
            if (x == 1){
                codi[1 << (i - 1)] |= 1 << (j - 1);
                //状态压缩，注意状压是反着的，所以左移(i - 1)就是状压的状态是 11000(而非题目第二个样例第一行的00011点四和五是在左边)
                //dodi表示当前这个点(这一行的i)能到达的点集(这一行的所有j)

            }
        }
        fr(i, 1, Maxs - 1){
            if (codi[i] == 0){//合并状态，把一个大状态分成一个点和其他的点集，因为状态从小到大枚举，所以两个状态一定被处理过
                codi[i] = codi[lowbit(i)] & codi[i ^ lowbit(i)];
            }
            if (fg[i])continue;
            for (Re j = codi[i];j;j = (j - 1) & codi[i]){
                fg[i | j] = 1;
                ans--;
            }
        }
        write(ans);
        ki;


    }

    return 0;
}
/*
 5
 0 0 0 1 1
 1 0 1 0 1
 1 0 0 1 0
 0 1 0 0 1
 0 0 1 0 0
共14个，so?
1
2
3
4
5
6(空集)
1 2 3 4 5
1 2 3 4
1 2 3 5
1 3 4 5
2 3 4 5
1 3 5
2 3 4
3 4 5
*/

  • \(codi[1 << (i - 1)] |= 1 << (j - 1);\)这一句的解释在代码里有，不再赘述

  • \(if (codi[i] == 0)\)
    这一句是现在这个状态没有被处理过，那就将他拆成一个单点和一堆小状态，将两个状态与一下，相当于题解所说的那步
    找到集合\(T\)

    • 为什么找交集?

      这张图,假如我们现在枚举到\([1, 2, 5, 3]\)这个子图,把它分成了\([1, 2, 3]\)这个强连通和\([5]\)这个单点，注意我们是要找出一个\(T\)保证它的子集和\(S\)或上一定是一个不强连通的，我们先要注意到题干的一句话满足任意两个不同的点之间均存在且仅存在一条有向边相连。所以两个点之间要不是指出要不是指入，如果我们找并集,那么一定有一个点它是可以指回去的，这样构成的\(S | R\)是一个强连通图，所以非法，只有找到交集，才能保证里边的点一定不会指回去

  • \(j = (j - 1)\) \(\&\) \(codi[i]\) 最后就是枚举T的子集了
    这个神仙操作可以枚举一个二进制的所有组合，也就是枚举它的所有子集，至于原理...手摸记住结论就行

  • 然后...这个题就被简单地切了

糖果

这个题吧，神仙dp,赛时\(神 · next\_permutation\)水了\(20pts\)

这个题\(Chen_jr\)写的很详细，就偷个懒粘一下了...
\(\%\%\%\)

点击查看代码 
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD long double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#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 frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_posair(x, y)
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 = 410, Mod = 1e9 + 7;
const int Inf = 2147483647;

// int wmx[maxn];
/*
她在夜里穿过我梦中的湖，在它的岸边，我看见过诸神漫步，而从湖心深处，我的魔法城堡升起。
她踩着梦幻阶梯，闯入我的不夜城
*/
int n, a[maxn], b[maxn];
int posa[maxn], posb[maxn];
LL dp[maxn][maxn][151][2];
int main(){
    n = read();
    fr(i, 1, n)a[i] = read(), posa[a[i]] = i;
    fr(i, 1, n)b[i] = read(), posb[b[i]] = i;
    LL ans = 0;
    dp[1][1][0][0] = 1;
    fr(i, 1, n + 1)
        fr(j, 1, n + 1)
        fr(k, 0, n / 3){
        if (dp[i][j][k][0]){
            if (i == n + 1){
                if (!k)ans = (ans + dp[i][j][k][0]) % Mod;
                continue;
            }
            if (posb[a[i]] < j)dp[i + 1][j][k][0] = (dp[i + 1][j][k][0] + dp[i][j][k][0]) % Mod;
            else{
                dp[i][j][k][1] = (dp[i][j][k][1] + dp[i][j][k][0]) % Mod;
                if (k)dp[i + 1][j][k - 1][0] = (dp[i + 1][j][k - 1][0] + dp[i][j][k][0] * k % Mod) % Mod;
            }
        }
        if (dp[i][j][k][1]){
            if (posa[b[j]] < i)dp[i][j + 1][k][1] = (dp[i][j + 1][k][1] + dp[i][j][k][1]) % Mod;
            else if (a[i] != b[j]){
                dp[i + 1][j + 1][k + 1][0] = (dp[i + 1][j + 1][k + 1][0] + dp[i][j][k][1]) % Mod;
                if (k)dp[i][j + 1][k - 1][1] = (dp[i][j + 1][k - 1][1] + dp[i][j][k][1] * k % Mod) % Mod;
            }
        }
    }
    fr(i, 1, n)if (i % 3)ans = ans * i % Mod;
    write(ans);
    return 0;
}
/*
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 1 4 5 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19
*/

树

其实就是染色呜呜呜

  • 这个题只要想明白维护一下时间戳，一条边两边的点时间不同就是黑色的就行(我只操作改白边)
点击查看代码 
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD long double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#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 frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr pair<long long, long long>
#define mk(x, y) make_pair(x, y)
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 = 5e5 + 10, Mod = 1e9 + 7;
const int Inf = 2147483647;
int q;
int head[maxn], len = 0;
int val[maxn];
struct Node{
    int to, next;
}wmx[maxn << 1];
fuc(void, Qian)(int from, int to){
    wmx[++len].to = to;
    wmx[len].next = head[from];
    head[from] = len;
}
int top[maxn], sz[maxn], son[maxn], dep[maxn], fa[maxn];
int id[maxn], rk[maxn];
int tim;
fuc(void, dfs1) (int x, int pre){
    sz[x] = 1;
    dep[x] = dep[pre] + 1;
    fa[x] = pre;
    for (Re i = head[x]; i; i = wmx[i].next){
        int to = wmx[i].to;
        if (to == pre)continue;
        dfs1(to, x);
        sz[x] += sz[to];
        if (sz[son[x]] < sz[to])son[x] = to;
    }
}
fuc(void, dfs2) (int x, int tp){
    top[x] = tp;
    rk[x] = ++tim;
    id[tim] = x;
    // id[rk] = val[x];
    if (!son[x])return;
    dfs2(son[x], tp);
    for (Re i = head[x]; i; i = wmx[i].next){
        int to = wmx[i].to;
        if (to != fa[x] && to != son[x])dfs2(to, to);
    }
}
int n;

struct Seg_Tree{
    int l, r;
    int sum;
    int lazy;
    int lcol, rcol;
}tr[maxn << 2];
#define lsp (rt << 1)
#define rsp (rt << 1 | 1)
#define lcol(rt) tr[rt].lcol
#define rcol(rt) tr[rt].rcol
#define sum(rt) tr[rt].sum
fuc(void, pushup)(int rt){
    tr[rt].sum = tr[lsp].sum + tr[rsp].sum;
    if (rcol(lsp) != lcol(rsp))sum(rt)++;
    lcol(rt) = lcol(lsp);
    rcol(rt) = rcol(rsp);
    return;
}
fuc(void, pushdown)(int rt){
    if (!tr[rt].lazy)return;
    int lz = tr[rt].lazy;
    lcol(lsp) = rcol(lsp) = lcol(rsp) = rcol(rsp) = lz;
    tr[lsp].lazy = lz;
    tr[rsp].lazy = lz;
    sum(lsp) = sum(rsp) = 0;
    tr[rt].lazy = 0;
    return;
}
fuc(void, build)(int rt, int l, int r){
    tr[rt].l = l;
    tr[rt].r = r;
    if (l == r){
        lcol(rt) = rcol(rt) = l;
        sum(rt) = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(lsp, l, mid);
    build(rsp, mid + 1, r);
    pushup(rt);
}
fuc(void, modify)(int rt, int L, int R, int k){
    int l = tr[rt].l, r = tr[rt].r;
    if (L <= l && r <= R){
        sum(rt) = 0;
        tr[rt].lazy = k;
        lcol(rt) = rcol(rt) = k;
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (L <= mid)modify(lsp, L, R, k);
    if (R > mid)modify(rsp, L, R, k);
    pushup(rt);
}

fuc(int, query)(int rt, int L, int R){
    int l = tr[rt].l, r = tr[rt].r;
    if (L <= l && r <= R)return  tr[rt].sum;
    pushdown(rt);
    int mid = (l + r) >> 1;
    int res = 0;
    if (L <= mid)res += query(lsp, L, R);
    if (R > mid)res += query(rsp, L, R);
    if (L <= mid && R > mid){
        if (lcol(rsp) != rcol(lsp))res++;
    }
    return  res;
}
fuc(int, check)(int rt, int pos){
    if (tr[rt].l == tr[rt].r){
        return  lcol(rt);
    }
    pushdown(rt);
    int l = tr[rt].l, r = tr[rt].r;
    int mid = (l + r) >> 1;
    if (pos <= mid)return  check(lsp, pos);
    else return  check(rsp, pos);
}

fuc(void, draw)(int x, int y, int k){
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        modify(1, rk[top[x]], rk[x], k);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y])swap(x, y);
    modify(1, rk[y], rk[x], k);
}
fuc(int, getans)(int x, int y){
    int res = 0;
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        res += query(1, rk[top[x]], rk[x]);
        if (check(1, rk[top[x]]) != check(1, rk[fa[top[x]]]))res++;
        x = fa[top[x]];
    }
    if (dep[x] < dep[y])swap(x, y);
    res += query(1, rk[y], rk[x]);
    return  res;
}
/*
她在夜里穿过我梦中的湖，在它的岸边，我看见过诸神漫步，而从湖心深处，我的魔法城堡升起。
*/

//如果是链的话那就是纯纯的树剖了
//不是，好像暴力树剖不就能行了嘛？
//先水一个链的
signed main(){
    n = read();
    fr(i, 1, n - 1){
        int x = read(), y = read();
        Qian(x, y);
        Qian(y, x);
        val[i] = 1;
    }
    val[n] = 1;
    q = read();
    dep[1] = 1;
    fa[1] = 1;
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    int timm = n + 1;
    // fr(i, 1, n){
    //     printf("tr[%d].sum = %d\n", i, tr[i].sum);
    // }
    // modify(1, 1, n - 1, 1);
    // printf("%d ", getsum(1, n) - 1);

    fr(i, 1, q){
        int optt = read();
        if (optt == 1){
            int x = read(), y = read();
            draw(x, y, timm);
            timm++;
            // fr(j, rk[x], rk[y]){
            //     int pos = id[rk[j]]

            // }
        }
        if (optt == 2){
            int x = read(), y = read();
            write(getans(x, y));//最后一个点权多加了
            ki;
        }
    }
    return  0;
}
/*
6
1 2
2 3
3 4
4 5
5 6
3
1 1 3
1 5 6
2 1 6
*/

标签：fr,putchar,int,地鼠,maxn,暑假,集训,dp,define
From： https://www.cnblogs.com/kiritokazuto/p/16584779.html

相关文章

  • 暑假集训五[星际旅行, 砍树, 超级树, 求和]
    暑假集训5星际旅行这个题刚看我觉得很ex，没事思路，就跳了，然后就去欺负\(T4\)了后来别的不会做，然后回来肝它...就肝出来了...对了，注意开\(longlong\)首先转化一下题意，我......
  • 暑假第七周总结
     集群启动(node1执行)格式化1hdfsnamenode-formatSH脚本一键启动12start-dfs.shstart-yarn.shSHELL日志目录**/export/server/hadoop-3.3......
  • 暑假集训一
    暑假集训1玩游戏其实是是一个很水的题，只要从k开始向左向右找到最远能到的点就行，最后如果是1和n就YES否则就NO,前缀和判一下就行..就是吧左开右闭的左边界加个1变成左闭右......
  • 雅礼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\)咋用来着？......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99