给定数组A,B，能否选取A中连续一段把A变得跟B相同
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define si signed
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define P pair<int,int>
int t,n;
int A[100000+5];
int B[100000+5];
signed main()
{
scanf("%I64d",&t);
while(t--){
scanf("%I64d",&n);
for(int i=0;i<n;i++){
scanf("%I64d",&A[i]);
}
for(int i=0;i<n;i++){
scanf("%I64d",&B[i]);
}
bool f=0;
int a=-1;
for(int i=0;i<n;i++){
A[i]=B[i]-A[i];
if(A[i]<0){
cout<<"No"<<endl;
f=1;
break;
}
}
int cnt =0;
if(!f){
for(int i=0;i<n;i++){
if(A[i]&&cnt==0){
cnt++;
while(i+1<n){
if(A[i]==A[i+1]){
i++;
}
else if(A[i]!=A[i+1]&&A[i+1]!=0){
puts("No");
f=1;
break;
}
else break;
}
}
else if(A[i]&&cnt!=0){
puts("No");
f=1;
break;
}
if(f) break;
}
if(!f)puts("Yes");
}
}
}
给定一个数组，要求给它分段
每一段出现了 i 必须出现 -i，且i要在-i之前出现
同一段不能出现两次相同的 i
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define si signed
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define P pair<int, int>
int t, n;
int A[100000 + 5];
int B[1000000 + 5];
vector<int> ans;
int C[1000000+5];
signed main()
{
t = 1;
while (t--)
{
scanf("%I64d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%I64d", &A[i]);
}
if (n & 1 || A[1] < 0)
{
puts("-1");
}
else
{
bool f = 0;
int cnt = 0;
ans.pb(0);
for (int i = 1; i <= n; i++)
{
if (A[i] < 0 && B[-A[i]] == 0)
{
puts("-1");
f = 1;
break;
}
else if (A[i] > 0)
{
B[A[i]]++;
C[A[i]]++;
cnt++;
if(C[A[i]]>1){
puts("-1");
f=1;
break;
}
}
else
{
B[-A[i]]--;
cnt--;
if (cnt == 0)
{
int t=ans[ans.size()-1];
ans.pb(i);
while(t<=i){///C数组复原
if(A[t]>0)C[A[t]]=0;
t++;
}
}
}
}
if (f==0&&cnt != 0)
{
cout << "-1" << endl;
f = 1;
}
if (!f)
{
cout << ans.size()-1 << endl;
for (int i = 0; i + 1 < ans.size(); i++)
{
cout << ans[i + 1] - ans[i] << ' ';
}
}
}
}
}
给定n个糖，每个糖有一个甜度值ai。
每天最多吃m个糖,第i天吃甜度为aj会产生aj*i的代价
输出n个数，第k个数代表吃k个糖最小总代价
排序后模拟 TLE
维护一下每次产生的元素 TLE
维护一下前缀 AC
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define si signed
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define P pair<int, int>
int t, n,m;
int A[200000 + 5];
int B[200000+5];
signed main()
{
scanf("%I64d%I64d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%I64d",&A[i]);
}
sort(A+1,A+1+n);
int ans=0;
for(int i=1;i<=n;i++){
int x=(i-1)/m+1;
int t=i%m;
if(i%m==0){
t=m;
}
int j=1;
B[t]+=A[t+(x-1)*m];///更新一下前缀
ans+=B[t];
cout<<ans<<' ';
}
}
给定一个无向图，顶点从1到 n
Harmonious Graph：若i<j，且i,j连通则 i与i+1,i+2，...j-1都要连通
求加多少边后能使该图变为Harmonious Graph
先找每个连通分量中的最大最小顶点
按最小顶点排序
从小到大把中间不连通的节点所在连通分量并进来
并查集维护一下连通关系
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define si signed
#define pb push_back
#define fi first
#define se second
#define endl '\n'
int t, n,m;
vector<int>G[200005];
int ma,mi;
int vis[200005];
void dfs(int x,int y)
{
for(int i=0;i<G[x].size();i++){
if(!vis[G[x][i]]){
vis[G[x][i]]=y;
mi=min(G[x][i],mi);
ma=max(G[x][i],ma);
dfs(G[x][i],y);
}
}
}
struct P{
int fi,se;
int id;
};
bool cmp(P a,P b)
{
return a.fi<b.fi;
}
P A[200005];
int fd(int x)
{
return (vis[x]==x?x:vis[x]=fd(vis[x]));
}
signed main()
{
int n,m;
scanf("%I64d%I64d",&n,&m);
int a,b;
for(int i=1;i<=m;i++){
scanf("%I64d%I64d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
int cnt=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=i;
mi=ma=i;
dfs(i,i);
A[cnt].fi=mi;
A[cnt].se=ma;
A[cnt++].id=i;
}
}
for(int i=1;i<=n;i++)if(!vis[i])vis[i]=i;
int _a=1,ans=0;
sort(A,A+cnt,cmp);
for(int i=0;i<cnt;i++){
if(A[i].fi==A[i].se)continue;
else if(A[i].se>_a){
for( _a=max(_a,A[i].fi);_a<=A[i].se;_a++){
if(fd(vis[A[i].id])!=fd(vis[_a])){
ans++;
vis[fd(vis[_a])]=fd(vis[A[i].id]);
}
}
}else continue;
}
cout<<ans<<'\n';
}
x轴上n个点，每个点有个辐射半径，[xi-si,xi+si]为其覆盖范围，辐射半径拓展1消耗代价为1
要把x轴上[1,m]的所有整点覆盖掉
求最小代价
dp[i]：表示下把从[1,i]所有整点覆盖掉的最小代价
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define si signed
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define sc(x) scanf("%I64d", &x);
int n, m;
int A[100005];
int B[100005];
int dp[100004];
si main()
{
sc(n)sc(m)
for(int i=1;i<=n;i++){
sc(A[i])sc(B[i])
}
for(int i=1;i<=m;i++){
dp[i]=1e18;
for(int j=1;j<=n;j++){
dp[i]=min(dp[i],min(max(max(abs(i-A[j])-B[j]/**要把i覆盖掉**/,0ll),(abs(1-A[j])-B[j])/**必须把1覆盖到**/),dp[A[j]-abs(i-A[j])-1<0?0:A[j]-abs(i-A[j])-1]/**dp[0]=0**/+max(abs(i-A[j])-B[j],0ll)));
}
}
cout<<dp[m]<<'\n';
}