CF580A
给出一个数列，求最长不下降子序列（连续）
直接DP，O(n)
CF580B
主人公有n个朋友，每一个朋友有2个属性：m，sat
现在他想邀请部分朋友，邀请的人满足MAX_M-MIN_M<d的条件下，使得sat之和最大
排序，前缀和，枚举左端点，二分右端点
O(NlogN)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream> #define ll long long using namespace std; const int maxn=1e5+; ll sum[maxn]; struct A
{
ll m,s;
};
A a[maxn]; bool cmp(A x,A y)
{
return x.m<y.m;
} void solve(int ,ll ); int main()
{
int n;
ll d;
scanf("%d %I64d",&n,&d);
for(int i=;i<=n;i++){
scanf("%I64d %I64d",&a[i].m,&a[i].s);
}
solve(n,d); return ;
} int bs(int i,int n,ll d)
{
int l=i;
int r=n;
while(l+<r){
int mm=(l+r)>>;
if(a[mm].m>=a[i].m+d)
r=mm;
else
l=mm;
}
if(a[r].m<a[i].m+d)
return r;
else
return l;
} void solve(int n,ll d)
{
sort(a+,a+n+,cmp); sum[]=;
for(int i=;i<=n;i++)
sum[i]=sum[i-]+a[i].s; ll ret=;
for(int i=;i<=n;i++){
int r=bs(i,n,d);
ret=max(ret,sum[r]-sum[i-]);
} cout<<ret<<endl;
return ;
}
CF580C
水题，直接dfs
#include<cstdio>
#include<cstring>
#include<algorithm> #define ll long long using namespace std; const int maxn=1e5+;
const int inf=0x3f3f3f3f; struct Edge
{
int to,next;
};
Edge edge[maxn<<];
int head[maxn];
int tot; int e[maxn][];
int out[maxn];
int val[maxn];
int dep[maxn]; void solve(int ,int ); void pre_init()
{
memset(head,-,sizeof head);
tot=;
} void addedge(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
} int main()
{
pre_init();
int n,m;
scanf("%d %d",&n,&m);
for(int i =;i<=n;i++)
scanf("%d",&val[i]);
for(int i=;i<n;i++){
scanf("%d %d",&e[i][],&e[i][]);
addedge(e[i][],e[i][]);
addedge(e[i][],e[i][]);
} solve(n,m); return ;
} void dfs(int u,int pre)
{
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(v==pre)
continue;
dep[v]=dep[u]+;
if(val[v])
val[v]+=val[u];
dfs(v,u);
}
} void dfs1(int u,int pre)
{
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(v==pre)
continue;
val[v]=max(val[v],val[u]);
dfs1(v,u);
}
} void solve(int n,int m)
{
memset(dep,,sizeof dep);
dfs(,-);
dfs1(,-);
memset(out,,sizeof out); for(int i=;i<n;i++){
if(dep[e[i][]]<dep[e[i][]])
out[e[i][]]++;
else
out[e[i][]]++;
} int ret=;
for(int i=;i<=n;i++){
if(!out[i] && val[i]<=m)
ret++;
}
printf("%d\n",ret);
return ;
}
CF577A
一个n*n的矩阵，maze[i][j]=i*j现在给出x，问x在矩阵中出现的次数
水题
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath> #define ll long long
#define ld long double using namespace std; int main()
{
ld n,x;
cin>>n>>x;
if(n*n<x){
cout<<<<endl;
return ;
}
int m=sqrt(x);
ll ans=;
bool flag=false;
if((ld)m*m==x){
ans++;
m--;
flag=true;
}
for(int i=;i<=m;i++){
if(i>n || i>x)
break;
if((ll)x%i== && ((ll)x/i)<=n){
ans++;
}
}
ans*=;
if(flag)
ans--;
cout<<ans<<endl;
return ;
}
CF579A
水题，答案为输入的数的二进制中，1的个数
CF579B
水题，一个排序就好了