240pts 题目比较简单 有AK机会但是我放弃了....
没开longlong 见祖宗.....
A 草地排水
时间限制 : - MS 空间限制 : - KB
评测说明 : 1s,256m
问题描述
【问题描述】 我们都知道，草地排水是一道简单的(usaco)网络流裸题。当然，网络流这么简单的知识点做这道题的各位大爷一定都很会做了。所以这道题和网络流并没有关系。
一场大雨过后，长春很多地势低洼的地方都被积水淹没了，(everlasting)家门口的草坪也不例外。脑小的(everlasting)当然不喜欢水啦，它找到了你去帮他家门口的草坪排水。
(everlasting)家门口的草坪可以近似的看作是一条一维直线。这条直线已经完全被积水淹没，你可以认为对于直线上的任意点，积水的深度都是无穷大的。(everlasting)有(n)个自动排水装置，对于每个自动排水装置，都有一个作用范围你可以选择任意多个装置使用，以期望得到最大的作用效果总和。但需要注意的是，任意两个装置的作用范围都不能有丝毫的重叠（即使区间端点重叠也是不被允许的）。若你的方案中存在重叠的作用范围，那萌萌的$everlasting (的家就会)BOOM$的一声炸到天上去！你一定不希望这么糟糕的事情发生吧！
解：
简单(DP)
离散化后定义 (f[j]) 代表以j结尾的最大的值
按照右端点从左到右排序 保证每次讨论的时候前面已经被算过了
这道题不能有选或不选的决策 也就是说j位置一定选了
(f[j]=max(f[k])+v;)
注意到(max(f[k]))是前缀最大值 所以树状数组前缀维护最大值就行了
还有一种单调队列的做法
按照起点从左到右排序
每次看结尾有那些在指定区域内都加上
然后单调队列维护一下就行了
code:
//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 200100
#define ll long long
#define GC getchar()
inline ll R() {
char t;
ll x=0;
t=GC;
while(!isdigit(t)) {
t=GC;
}
while(isdigit(t)) {
x=x*10+t-'0';
t=GC;
}
return x;
}
ll f[maxnn];
ll n;
#define lowbit(i) i&(-i)
ll c[maxnn];
void add(ll x,ll d) {
for(int i=x; i<=n+100100; i+=lowbit(i)) {
c[i]=max(c[i],d);
}
}
ll get(ll x) {
ll ans=0;
for(int i=x; i; i-=lowbit(i)) {
ans=max(c[i],ans);
}
return ans;
}
struct node {
ll fir,sec,v;
} a[maxnn];
bool cmp(node a,node b) {
return a.sec<b.sec;
}
ll d[maxnn],cnt;
int main() {
//freopen("water.in","r",stdin);
//freopen("water.out","w",stdout);
n=R();
for(int i=1; i<=n; i++) {
a[i].fir=R();
a[i].sec=R();
a[i].v=R();
d[++cnt]=a[i].fir;
d[++cnt]=a[i].sec;
}
sort(d+1,d+1+cnt);
ll r=unique(d+1,d+1+cnt)-d;
for(int i=1; i<=n; i++) {
a[i].fir=lower_bound(d+1,d+r,a[i].fir)-d;
a[i].sec=lower_bound(d+1,d+r,a[i].sec)-d;
}
sort(a+1,a+1+n,cmp);
ll ans=0;
for(int i=1; i<=n; i++) {
f[a[i].sec]=max(f[a[i].sec],get(a[i].fir-1)+a[i].v);
add(a[i].sec,f[a[i].sec]);
ans=max(ans,f[a[i].sec]);
}
cout<<ans;
}
B 化学
时间限制 : - MS 空间限制 : - KB
评测说明 : 1s,256m
解:
折半搜索或者分段打表
然后我考试的时候以为对拍了就稳了 然后就没有静态差错更加没有看全数据范围 (m ≤ 10^18) (1 ≤q≤ 10^18)
上次考试也是这样 数据范围没有看 然后就想当然地以为对拍了就没有错 真是失智
看完题目一定要看数据范围 加亮标记 题目要读三遍！！！ 最后检查的时候一定要看wan数据范围一定要静态查错....
附上代码:
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxnn 60
vector<ll> Q1,Q2;
ll n,m;
ll all1,all2;
ll e1[maxnn],e2[maxnn];
ll p[maxnn];
#define GC getchar()
inline ll R() {
char t;
ll x=0;
t=GC;
while(!isdigit(t)) {
t=GC;
}
while(isdigit(t)) {
x=x*10+t-'0';
t=GC;
}
return x;
}
int main()
{
//freopen("chemistry.in","r",stdin);
//freopen("chemistry.out","w",stdout);
n=R();m=R();
for(int i=1;i<=n;i++)
{
p[i]=R();
}
ll d1=n/2;
all1=(1LL<<d1)-1;
ll d2=n-d1;
all2=(1LL<<d2)-1;
for(int i=1;i<=d1;i++)
{
e1[i]=p[i];
}
ll num=0;
for(int i=d1+1;i<=n;i++)
{
e2[++num]=p[i];
}
for(int i=0;i<=all1;i++)
{
ll d=0;
for(int j=1;j<=d1;j++)
{
if(i&(1<<j-1))
{
d+=e1[j];
}
}
Q1.push_back(d);
}
for(int i=0;i<=all2;i++)
{
ll d=0;
for(int j=1;j<=d2;j++)
{
if(i&(1<<j-1))
{
d+=e2[j];
}
}
Q2.push_back(d);
}
sort(Q1.begin(),Q1.end());
sort(Q2.begin(),Q2.end());
ll ans=0;
for(int i=0;i<Q1.size();i++)
{
int d=Q2.size();
d--;
if(Q2[d]<=(m-Q1[i])) {ans+=d+1;continue;}
ans+=upper_bound(Q2.begin(),Q2.end(),m-Q1[i])-Q2.begin();
}
cout<<ans;
}
C 读书
时间限制 : - MS 空间限制 : - KB
评测说明 : 1s,256m
解：
贪心一下 考虑链就行了
code：
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxnn 1000010
int size[maxnn];
int T;
int n;
int f[maxnn][24];
#define GC getchar()
inline ll R() {
char t;
ll x=0;
t=GC;
while(!isdigit(t)) {
t=GC;
}
while(isdigit(t)) {
x=x*10+t-'0';
t=GC;
}
return x;
}
int las[maxnn],en[maxnn],le[maxnn],tot,nex[maxnn];
int dep[maxnn];
void add(int a,int b) {
en[++tot]=b;
nex[tot]=las[a];
las[a]=tot;
}
int goup(int x,int k) {
int s=log2(n);
for(int i=s; i>=0; i--) {
if((1<<i)&k) {
x=f[x][i];
}
}
return x;
}
void dfs1(int v,int fa) {
dep[v]=dep[fa]+1;
f[v][0]=fa;
size[v]=1;
int s=log2(n);
for(int i=1; i<=s; i++) {
f[v][i]=f[f[v][i-1]][i-1];
}
for(int i=las[v]; i; i=nex[i]) {
int u=en[i];
if(u!=fa) {
dfs1(u,v);
size[v]+=size[u];
}
}
}
void clear()
{
memset(las,0,sizeof(las));
tot=0;
memset(size,0,sizeof(size));
memset(dep,0,sizeof(dep));
memset(f,0,sizeof(f));
}
void FIE()
{
freopen("book.in","r",stdin);
freopen("book.out","w",stdout);
}
int main() {
//FIE();
T=R();
while(T--) {
clear();
n=R();
int x,y;
for(int i=1; i<n; i++) {
x=R();
y=R();
add(x,y);
add(y,x);
}
dfs1(1,1);
int tmp1=0;
int tmp2=0;
int d=(dep[n]-dep[1]-1)/2;
int r=goup(n,d);
tmp2=size[r];
tmp1=n-size[r];
puts(tmp1>tmp2?"^_^":"T_T");
}
}
下次再不看数据范围我就》》》
不要以为对拍就没事 要静态查错注意数据范围