A 最短路
待补
B组队
排序后，二分大于当前这个数的第一个位置，更新最大值即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
int main()
{
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
vector<ll> a(n+1);
map<ll,int> mp;
ll ma=-2e9,mi=2e9;
for(int i=1;i<=n;i++) cin>>a[i],ma=max(ma,a[i]),mi=min(mi,a[i]);
sort(a.begin()+1,a.end());
int ans=0;
for(int i=1;i<=n;i++){
int p=upper_bound(a.begin()+1,a.end(),a[i]+k)-a.begin();
ans=max(ans,p-i);
}
cout<<ans<<endl;
}
return 0;
} C十面埋伏
对‘#’外围的'.'全都打上标记，然后看标记的周围是不是有’#'，有的话变成‘*’即可
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[505][505];
bool vis[505][505];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int check(int x,int y){
if(x<0 || x>=n || y<0 || y>=m || vis[x][y] || s[x][y]=='#') return 1;
return 0;
}
void dfs(int x,int y){
vis[x][y]=1;
for(int i=0;i<4;i++){
int fx=x+dx[i],fy=y+dy[i];
if(check(fx,fy)) continue;
dfs(fx,fy);
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>s[i];
dfs(0,0);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(vis[i][j]){
int cnt=0;
if(i>=1 && s[i-1][j]=='#') cnt++;
if(j>=1 && s[i][j-1]=='#') cnt++;
if(i+1<n && s[i+1][j]=='#') cnt++;
if(j+1<m && s[i][j+1]=='#') cnt++;
if(cnt) s[i][j]='*';
}
}
}
for(int i=0;i<n;i++) cout<<s[i]<<endl;
return 0;
} D牛妹吃豆子
二维差分+二维前缀和
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll c[2005][2005],n,m;
int main()
{
ios::sync_with_stdio(0);
int k,q;cin>>n>>m>>k>>q;
while(k--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
c[x1][y1]++;
c[x2+1][y2+1]++;
c[x1][y2+1]--;
c[x2+1][y1]--;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
}
}
while(q--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<c[x2][y2]-c[x1-1][y2]-c[x2][y1-1]+c[x1-1][y1-1]<<endl;
}
return 0;
}
E旅旅旅游
正反分别跑一次最短路，枚举每条边是不是最短路的必经的边，不是的话，并查集合并点集，最后看是不是1~n在同一个集合
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n, m;
ll f[1<<17];
ll find(ll x){
return f[x]==x?x:f[x]=find(f[x]);
}
struct dijkstra
{
struct node
{
ll to, cost;
friend bool operator<(node a, node b)
{
return a.cost > b.cost;
}
};
ll d[1<<17];
ll e[1<<20], v[1<<20], ne[1<<20], h[1<<20], idx;
bool vis[1<<17];
void Init()
{
memset(h, -1, sizeof h);
}
void add(ll a, ll b, ll c)
{
e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dj(ll x, ll y)
{
for (ll i = 1; i <= n; i++)
d[i] = -1, vis[i] = 0;
priority_queue<node> q;
q.push({x, 0});
while (!q.empty())
{
node now = q.top();
q.pop();
if (!vis[now.to])
{
vis[now.to] = 1;
d[now.to] = now.cost;
for (ll i = h[now.to]; i != -1; i = ne[i])
{
node next;
next.to = e[i];
next.cost = now.cost + v[i];
if (!vis[next.to])
q.push(next);
}
}
}
}
} a,b;
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(ll i=1;i<=n;i++) f[i]=i;
a.Init(),b.Init();
for(ll i=1; i<=m; i++)
{
ll x,y,d;
cin>>x>>y>>d;
a.add(x,y,d),a.add(y,x,d);
b.add(x,y,d),b.add(y,x,d);
}
a.dj(1,n);
b.dj(n,1);
ll mi=a.d[n];
for(ll i=1;i<=n;i++){
for(ll j=a.h[i];~j;j=a.ne[j]){
if(mi==a.d[i]+b.d[a.e[j]]+a.v[j] || mi==a.d[a.e[j]]+b.d[i]+a.v[j]) continue;
f[find(i)]=find(a.e[j]);
}
}
ll fa=find(1);
ll num=1;
for(ll i=1;i<=n;i++) if(fa!=find(i)) num++;
cout<<(num==1?"YES":"NO")<<endl;
return 0;
}
F斗兽棋
签到
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
int main()
{
string a,b;
cin>>a>>b;
if(b=="elephant"&&a=="tiger" || b=="tiger"&&a=="cat" || b=="cat"&&a=="mouse" || b=="mouse"&&a=="elephant")
cout<<"tiangou txdy";
else cout<<"tiangou yiwusuoyou";
return 0;
}
G做题
排序后从最小的开始取
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
int main()
{
ll n,k;
cin>>n>>k;
vector<ll> a(n+1);
for(int i=1; i<=n; i++)cin>>a[i];
sort(a.begin()+1,a.end());
int ans=0;
for(int i=1;i<=n;i++){
if(k>=a[i]){
ans++;k-=a[i];
}
}
cout<<ans<<endl;
return 0;
} H人人都是好朋友
离散化后，对于朋友进行集合合并，把朋友处理完后，对敌人进行查询是不是在同一个集合
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
#define rson mid + 1, r, rt << 1 | 1
#define lson l, mid, rt << 1
const ll maxn=1e6+5;
int f[maxn<<1];
struct node
{
int a,b,c;
}a[maxn],b[maxn];
int q[maxn<<1];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void join(int x,int y){
x=find(x),y=find(y);
if(x!=y) f[x]=y;
}
int main() {
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--){
int n;cin>>n;
int cnt=0;
for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b>>a[i].c,q[++cnt]=a[i].a,q[++cnt]=a[i].b;
sort(q+1,q+1+cnt);
int len=unique(q+1,q+1+cnt)-q-1;
for(int i=1;i<=(n<<1);i++) f[i]=i;
cnt=0;
for(int i=1;i<=n;i++){
int x=lower_bound(q+1,q+len+1,a[i].a)-q;
int y=lower_bound(q+1,q+len+1,a[i].b)-q;
int id=a[i].c;
if(id==1) {
join(x,y);
}
else b[++cnt]={x,y,id};
}
int flag=0;
for(int i=1;i<=cnt;i++){
if(find(b[i].a)==find(b[i].b)){
flag=1;break;
}
}
if(flag) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
I求和
树上操作，而且只是单点更新和区间求和。
dfs序把树形结构变为线性结构，树状数组维护即可。
如果有区间更新套线段树即可
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long ll;
ll a[1<<20];
ll c[1<<20],in[1<<20],out[1<<20];
ll time;
ll n,q,root;
ll tot,head[1<<21];
struct node {
ll to, next;
} edge[1<<21];
void add(ll u, ll v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void up(ll x,ll v){
for(;x<=n;x+=x&(-x)) c[x]+=v;
}
ll get(ll x){
ll ans=0;
for(;x;x-=x&(-x)) ans+=c[x];
return ans;
}
void dfs(ll x,ll f){
in[x]=++time;
for (ll i = head[x]; i != -1; i = edge[i].next){
ll it=edge[i].to;
if(it==f) continue;
dfs(it,x);
}
out[x]=time;
}
int main(){
memset(head,-1,sizeof head);
scanf("%lld%lld%lld",&n,&q,&root);
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
for(ll i=1;i<n;i++){
ll x,y;scanf("%lld%dll",&x,&y);
add(x,y),add(y,x);
}
dfs(root,-1);
for(ll i=1;i<=n;i++) up(in[i],a[i]);
while(q--){
ll op,x;scanf("%lld%lld",&op,&x);
if(op==1){
ll y;scanf("%lld",&y);
up(in[x],y);
}
else printf("%lld\n",get(out[x])-get(in[x]-1));
}
return 0;
}
J建设道路
简单数学推公式
两两之间进行计算，也就是有
种，那么因为每种都会处理出来两个平方项，总共就处理出来了
)
总共有n个点，所有每个点的平方和进行增加了n-1次
考虑减去的 对于下标为1的时候减去的是)
对于下标为2减去的就是)
显然处理一个后缀和遍历即可。注意取模
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
const ll mod=1e9+7;
ll a[1<<20];
int main()
{
int n;cin>>n;
ll sum=0;
for(int i=1;i<=n;i++)cin>>a[i],sum=(sum+(n-1)*a[i]%mod*(a[i]%mod))%mod;
for(int i=n-1;i;i--){
sum=((sum-((2*a[i])%mod*(a[i+1]%mod)%mod))%mod+mod)%mod;
a[i]+=a[i+1];
}
cout<<(sum%mod+mod)%mod;
return 0;
}
京公网安备 11010502036488号