https://ac.nowcoder.com/acm/contest/5158#question
组队【二分】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5*3+10;
int a[N],t,n,k;
int main(void)
{
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int ans=0;
for(int i=0;i<n;i++)
{
int temp=a[i]+k;
int l=i,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(a[mid]<=temp) l=mid;
else r=mid-1;
}
ans=max(ans,l-i+1);
}
cout<<ans<<'\n';
}
return 0;
}
滑动窗口
#include<bits/stdc++.h>
using namespace std;
const int N=1e5*3+10;
int a[N],t,n,k;
int main(void)
{
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int ans=0;
queue<int>q; q.push(a[0]);
for(int i=1;i<n;i++)
{
q.push(a[i]);
while(q.front()+k<q.back()) q.pop();
ans=max(ans,(int)q.size());
}
cout<<ans<<'\n';
}
return 0;
}
十面埋伏【bfs】
bfs一下，让在外面的都标记一下。然后对于标记的看四周有没有即可。有的话就加。
#include<bits/stdc++.h>
using namespace std;
const int N=550;
string s[N];
int n,m,st[N][N];
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
bool solve(int x,int y)
{
int cnt=0;
for(int i=0;i<4;i++)
{
int tempx=x+dx[i],tempy=y+dy[i];
if(tempx<0||tempx>=n||tempy<0||tempy>=m) continue;
if(s[tempx][tempy]=='#') cnt++;
}
return cnt;
}
void bfs()
{
st[0][0]=1;
queue< pair<int,int> >q; q.push( {0,0} );
while(q.size())
{
auto temp=q.front(); q.pop();
int x=temp.first,y=temp.second;
for(int i=0;i<4;i++)
{
int tempx=x+dx[i],tempy=y+dy[i];
if(tempx<0||tempx>=n||tempy<0||tempy>=m) continue;
if(s[tempx][tempy]=='#') continue;
if(st[tempx][tempy]) continue;
q.push({tempx,tempy});st[tempx][tempy]=1;
}
}
}
int main(void)
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>s[i];
bfs();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(st[i][j]&&solve(i,j)) cout<<'*';
else cout<<s[i][j];
}
puts("");
}
return 0;
}
牛妹吃豆子【差分 前缀和】
#include<bits/stdc++.h>
using namespace std;
const int N=1e3*2+10;
typedef long long int LL;
LL s[N][N],n,m,k,q;
void add(int x,int y,int xx,int yy,int c)
{
s[x][y]+=c;
s[x][yy+1]-=c;
s[xx+1][y]-=c;
s[xx+1][yy+1]+=c;
}
void init(int n,int m)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
LL query(int x,int y,int xx,int yy)//(x,y)矩阵的左上角的坐标，(xx,yy)矩阵右下角的坐标
{
LL sum=s[xx][yy]-s[x-1][yy]-s[xx][y-1]+s[x-1][y-1];
return sum;
}
int main(void)
{
cin>>n>>m>>k>>q;
while(k--)
{
int x,y,xx,yy; cin>>x>>y>>xx>>yy;
add(x,y,xx,yy,1);
}
init(n,m),init(n,m);
while(q--)
{
int x,y,xx,yy; cin>>x>>y>>xx>>yy;
cout<<query(x,y,xx,yy)<<'\n';
}
return 0;
}
旅旅旅游【判断这条边是不是最短路上的边】
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int M=1e6+10;
typedef long long int LL;
typedef pair<LL,int> PII;
LL h[N],e[M],ne[M],w[M],idx;
LL p[N];
LL dist1[N],dist2[N],n,m,st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void Dijkstra(LL dist[],int u)
{
memset(dist,0x3f,sizeof dist1);
memset(st,0,sizeof st);
dist[u]=0;
priority_queue<PII,vector<PII>,greater<PII>>q; q.push({0,u});
while(q.size())
{
auto temp=q.top(); q.pop();
int u=temp.second;
if(st[u]) continue;
st[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[u]+w[i])
{
dist[j]=dist[u]+w[i];
q.push({dist[j],j});
}
}
}
}
struct node{int a,b,c;};
vector<node>ve;
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(void)
{
memset(h,-1,sizeof h);
cin>>n>>m;
while(m--)
{
int a,b,c; scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
ve.push_back({a,b,c});
}
Dijkstra(dist1,1);
Dijkstra(dist2,n);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<ve.size();i++)
{
int a=ve[i].a,b=ve[i].b,c=ve[i].c;
if(dist1[a]+dist2[b]+c==dist1[n]) continue;
if(dist2[a]+dist1[b]+c==dist1[n]) continue;
p[find(a)]=find(b);
}
set<int>st;
for(int i=1;i<=n;i++) st.insert(find(i));
if(st.size()==1) puts("YES");
else puts("NO");
return 0;
}
斗兽棋
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long int LL;
int check(string a,string b)
{
if(a=="elephant"&&b=="tiger") return 1;
if(a=="tiger"&&b=="cat") return 1;
if(a=="cat"&&b=="mouse") return 1;
if(a=="mouse"&&b=="elephant") return 1;
if(b=="elephant"&&a=="tiger") return 0;
if(b=="tiger"&&a=="cat") return 0;
if(b=="cat"&&a=="mouse") return 0;
if(b=="mouse"&&a=="elephant") return 0;
return 1;
}
int main(void)
{
string a,b; cin>>a>>b;
if(check(a,b)) puts("tiangou yiwusuoyou");
else puts("tiangou txdy");
return 0;
}
做题
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long int LL;
LL s[N],n,m;
int main(void)
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>s[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) s[i]=s[i]+s[i-1];
int ans=0;
for(int i=1;i<=n;i++)
{
if(s[i]<=m) ans=i;
}
cout<<ans;
return 0;
}
人人都是好朋友【并查集+离散化】
先处理朋友，再处理不是朋友。
注意离散化不然会TLE.
#include<bits/stdc++.h>
using namespace std;
struct node{int a,b,c;};
int p[10001000];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(void)
{
int t; scanf("%d",&t);
while(t--)
{
int n; scanf("%d",&n);
vector<node>ve1,ve2;
vector<int>ve;
for(int i=0;i<n;i++)
{
int a,b,c; scanf("%d%d%d",&a,&b,&c);
if(c) ve1.push_back({a,b,c});
else ve2.push_back({a,b,c});
ve.push_back(a),ve.push_back(b);
}
sort(ve.begin(),ve.end());
ve.erase(unique(ve.begin(),ve.end()),ve.end());
for(int i=0;i<ve.size();i++) p[i]=i;
for(int i=0;i<ve1.size();i++)
{
int a=lower_bound(ve.begin(),ve.end(),ve1[i].a)-ve.begin();//找到离散化后的坐标
int b=lower_bound(ve.begin(),ve.end(),ve1[i].b)-ve.begin();
p[find(a)]=find(b);
}
bool flag=1;
for(int i=0;i<ve2.size();i++)
{
int a=lower_bound(ve.begin(),ve.end(),ve2[i].a)-ve.begin();
int b=lower_bound(ve.begin(),ve.end(),ve2[i].b)-ve.begin();
if(find(a)==find(b)) flag=0;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
求和【dfs序+树状数组】
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e6+10;
const int M=1e6*2+10;
LL h[N],e[M],ne[M],idx;
LL tr[N],in[N],out[N],w[N],timestep;
int n,m,root;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{
in[u]=++timestep;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs(j,u);
}
out[u]=timestep;
}
int lowbit(int x){return x&(-x);}
void update(int x,LL v)
{
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}
LL query(int x)
{
LL sum=0;
for(int i=x;i;i-=lowbit(i)) sum+=tr[i];
return sum;
}
int main(void)
{
memset(h,-1,sizeof h);
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
for(int i=1;i<=n-1;i++)
{
int a,b; scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
dfs(root,-1);
for(int i=1;i<=n;i++) update(in[i],w[i]);//in[i] i号结点在dfs序列中的位置
while(m--)
{
int op; scanf("%d",&op);
if(op==1)
{
LL u,x; scanf("%lld%lld",&u,&x);
update(in[u],x);
}else
{
LL u; scanf("%lld",&u);
printf("%lld\n",query(out[u])-query(in[u]-1));
}
}
return 0;
}
建设道路【推式子】
a1 a2 a3 a4
a1a2,a1a3,a1a4,a2a3,a2a4,a3a4=(n-1)a1^2+(n-1)a2^2+(n-1)a3^2+(n-1)a4^2-2*a1*(a2+a3+a4)-2*a2(a3+a4)-2*a3*a4
#include<bits/stdc++.h>
using namespace std;
const int N=1e5*5+10;
const int mod=1e9+7;
typedef long long int LL;
LL a[N],s[N],n;
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=(s[i-1]+a[i])%mod;
LL sum=0;
for(int i=1;i<=n;i++)
{
LL temp1=(a[i]*a[i])%mod*(n-1)%mod;
sum=(sum+temp1)%mod;
LL temp2=2*a[i]*(s[n]-s[i])%mod;
sum=(sum+mod-temp2)%mod;
}
cout<<sum;
return 0;
}
