专栏文章

刷题记录

yyisit
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minbh6nh
此快照首次捕获于
2025/12/01 23:41
3 个月前
此快照最后确认于
2025/12/01 23:41
3 个月前
查看原文

P1569Generic Cow Protests

题意

nn 个数字，分成 xx 段使得每一段的和都 ≥0\ge 0。

思路

dp+前缀和
设 dpidp_i 表示前 ii 个数可以被分成的最大区间数。
首先如果 ∑i=1nai<0\sum_{i=1}^{n}a_i< 0，那么一定输出 Impossible；
枚举每个点 ii 和它前面的点 jj，如果 ∑k=ji≥0\sum_{k=j}^i\ge 0，即 sumi−sumj−1≥0sum_i -sum_{j-1}\ge 0，说明这个区间是满足的，就可以转移：
dpi=max⁡(dpi,dpj+1)dp_i=\max(dp_i,dp_j+1)
  • dpidp_i：当前区间的答案。
  • dpj+1dp_j+1：本来前 jj 段的答案再加上 j∼ij\sim i 这段。

代码

CPP
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define il inline
#define endl '\n'
#define ull unsigned long long
#define llt __int128
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x)*(y)/(gcd(x,y))) 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define fff(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#define ls (k<<1)
#define rs (k<<1|1)
#define umap unordered_map
#define uset unordered_set
#define mmap multimap
#define mset multiset
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define psi pair<string,int>
#define psl pair<string,long long>
#define numpy(a,n) a+1,a+n+1
#define fi first
#define se second
#define clr(a) memset(a,0,sizeof(a))
#define mem(a,v)	memset(a,v,sizeof(a))
#define lowbit(x) (x&(-x))
#define all(s) s.begin(),s.end()
#define mkp make_pair
#define maxi INT_MAX
#define maxl LONG_LONG_MAX
#define mini INT_MIN
#define minl LONG_LONG_MIN
#define sss "--------------------------------------------------"
//-----------------------------------------------------------------------------
const int N=1005;
int a[N],sum[N],dp[N];
signed main(){
//	fff("")
	IOS
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=a[i]+sum[i-1];
        if(sum[i]) dp[i]=1;
	}
	mem(dp,-0x3f3f3f);
	dp[0]=0;
    if(sum[n]<0){
        cout<<"Impossible";
        return 0;
    }
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			if(sum[i]-sum[j]>=0){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	cout<<dp[n];
	return 0;	
}

P11962 [GESP202503 六级] 树上漫步

DFS+一点优化

题意

树上的一个节点走偶数步可以到达的节点个数。

思路

首先看到题目就知道暴力枚举 O(n2)O(n^2) 可以拿 40×1440\times \frac{1}{4} 分，具体写法不说。
我们可以先求出每一个节点的深度，随后可以发现如果第 ii 个节点的深度是偶数，那么经过偶数步可以到达深度同为偶数的节点，包括自己，奇数点同理。所以只要 O(n)+O(n)+O(n)O(n)+O(n)+O(n) 即可，复杂度 O(n)O(n)。

代码

CPP
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define lb long double
#define il inline
#define endl '\n'
#define ull unsigned long long
#define llt __int128
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x)*(y)/(gcd(x,y))) 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define fff(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#define ls (k<<1)
#define rs (k<<1|1)
#define umap unordered_map
#define uset unordered_set
#define mmap multimap
#define mset multiset
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define psi pair<string,int>
#define psl pair<string,long long>
#define gc getchar
#define numpy(a,n) a+1,a+n+1
#define fi first
#define copy(a,b) memcpy(a,b,sizeof(a))
#define se second
#define clr(a) memset(a,0,sizeof(a))
#define mem(a,v)	memset(a,v,sizeof(a))
#define lowbit(x) (x&(-x))
#define all(s) s.begin(),s.end()
#define mkp make_pair
#define maxi INT_MAX
#define maxl LONG_LONG_MAX
#define mini INT_MIN
#define minl LONG_LONG_MIN
#define debug(x) cerr<<#x<<"="<<(x)<<'\n' 
#define hmod 212370440130137957ll
#define sss "--------------------------------------------------"
//-----------------------------------------------------------------------------
int n;
const int N=2e5+5;
int head[N],nxt[N<<1],to[N<<1],cnt=1;
il void add(int u,int v){
	nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
}
int dep[N];
int cnt1,cnt2;
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v!=fa)	dfs(v,u);
	}
}
signed main(){
//	fff("")
	IOS
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	// for(int i=1;i<=n;i++)	cout<<dep[i]<<" ";
	for(int i=1;i<=n;i++){
		if(dep[i]%2==0){
			cnt1++;
		}
		else cnt2++;
	}
	for(int i=1;i<=n;i++){
		if(dep[i]%2==0){
			cout<<cnt1<<" ";
		}
		else cout<<cnt2<<" ";
	}
	return 0;	
}	
//CODE BY tc291311 Luogu uid1340395 in Windows-VScode

P1296 奶牛的耳语

题意

找出距离不超过 dd 的二元组对数。

思路

考虑暴力枚举每一个数和它后面的数，时间复杂度 O(n2)O(n^2)，80pts80pts。
我们可以用 upper_bound 函数找出对于每一个 ai+da_i+d 第一个大于它的数，再用这个数减去 ii 再 −1-1 就是第 ii 个数可以到达的点，不懂？看看样例：
10,12,16,37,4010 ,12 ,16 ,37 ,40
  1. 第一个大于 2020 的数是 3737，坐标是 44，4−1−1=24-1-1=2
  2. 第一个大于 2222 的数是 3737，坐标是 44，4−2−1=14-2-1=1
看懂没有？本来从第一个大于 ai+da_i+d 的数到 ii 的距离是 x−i+1x-i+1，xx 表示为第一个大于 ai+da_i+d 的数的坐标，因为 ax>ai+da_x>a_i+d，所以实际能到的是 x−ix-i，但是自己又不能和自己说话，所以就是 x−i−1x-i-1 了。

代码

CPP
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define lb long double
#define il inline
#define endl '\n'
#define ull unsigned long long
#define llt __int128
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x)*(y)/(gcd(x,y))) 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define fff(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#define ls (k<<1)
#define rs (k<<1|1)
#define umap unordered_map
#define uset unordered_set
#define mmap multimap
#define mset multiset
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define psi pair<string,int>
#define psl pair<string,long long>
#define gc getchar
#define numpy(a,n) a+1,a+n+1
#define fi first
#define copy(a,b) memcpy(a,b,sizeof(a))
#define se second
#define clr(a) memset(a,0,sizeof(a))
#define mem(a,v)	memset(a,v,sizeof(a))
#define lowbit(x) (x&(-x))
#define all(s) s.begin(),s.end()
#define mkp make_pair
#define maxi INT_MAX
#define maxl LONG_LONG_MAX
#define mini INT_MIN
#define minl LONG_LONG_MIN
#define debug(x) cerr<<#x<<"="<<(x)<<'\n' 
#define hmod 212370440130137957ll
#define sss "--------------------------------------------------"
//-----------------------------------------------------------------------------
const int N=1e6+5;
int a[N];
ll ans;
int n,d;
signed main(){
//	fff("")
	IOS
	cin>>n>>d;
	for(int i=1;i<=n;i++)	cin>>a[i];
	sort(numpy(a,n));
	for(int i=1;i<=n;i++){
		ll r=upper_bound(numpy(a,n),a[i]+d)-a;
		ll l=i;
		ans+=(r-l-1);
	}
	cout<<ans;
	return 0;	
}	
//CODE BY tc291311 Luogu uid1340395 in Windows-VScode

P1194 买礼物

kruskal+一点思维

题意

明明需购买 BB 样单价均为 AA 元的物品，购买第 II 样后再买第 JJ 样可享优惠价 KI,JK_{I,J}（KI,J=KJ,IK_{I,J}=K_{J,I}，00 表示无优惠，可能大于 AA）。求购买所有物品的最小总花费。

思路

kruskal 的板子。
目标是把所有节点连接起来，求最小的权值。
先用一个主节点 00 把所有点连接，边权均为 AA。
  • 如果此时 K=0K=0：不管。
  • 如果此时 K≠0K\neq0：连接一条从 ii 到 jj 边权为 Ki,jK_{i,j} 的边。
再跑一边 kruskal 即可。

代码

CPP
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define lb long double
#define il inline
#define endl '\n'
#define ull unsigned long long
#define llt __int128
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x)*(y)/(gcd(x,y))) 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define fff(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#define ls (k<<1)
#define rs (k<<1|1)
#define umap unordered_map
#define uset unordered_set
#define mmap multimap
#define mset multiset
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define psi pair<string,int>
#define psl pair<string,long long>
#define gc getchar
#define numpy(a,n) a+1,a+n+1
#define fi first
#define copy(a,b) memcpy(a,b,sizeof(a))
#define se second
#define clr(a) memset(a,0,sizeof(a))
#define mem(a,v)	memset(a,v,sizeof(a))
#define lowbit(x) (x&(-x))
#define all(s) s.begin(),s.end()
#define mkp make_pair
#define maxi INT_MAX
#define maxl LONG_LONG_MAX
#define mini INT_MIN
#define minl LONG_LONG_MIN
#define debug(x) cerr<<#x<<"="<<(x)<<'\n' 
#define hmod 212370440130137957ll
#define sss "--------------------------------------------------"
//-----------------------------------------------------------------------------
const int N=5e5+5;
struct node{
    int u,v,w;
}a[N];
int ans;
int cnt;
int fa[N];
int find(int u){
    if(u==fa[u])    return u;
    return fa[u]=find(fa[u]);
}
void merge(int u,int v){
    fa[find(u)]=find(v);
}
bool cmp(node x,node y){
    return x.w<y.w;
}
void kruskal(){
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
        if(find(a[i].v)==find(a[i].u))  continue;
        merge(a[i].v,a[i].u);
        ans+=a[i].w;
    }
}
signed main(){
//	fff("")
	IOS
	int v,n;
    cin>>v>>n;
    for(int i=1;i<=n;i++){
        a[++cnt].u=0;
        a[cnt].v=i;
        a[cnt].w=v;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int k;
            cin>>k;
            if(k!=0){
                a[++cnt].u=i;
                a[cnt].v=j;
                a[cnt].w=k;
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        fa[i]=i;
    }
    kruskal();
    cout<<ans;
    return 0;	
}	
//CODE BY tc291311 Luogu uid1340395 in Windows-VScode

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...