【SinGuLaRiTy-1031】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
对于所有题目: Time Limit: 1s | Memory Limit: 128 MB
膜拜azui (azui)
题目描述
一天，小A给了J·G一道水题，一道水题，J·G一眼秒了，现在 J·G想考考你们：
小A有N个灯，排成了一列，现在小 A给出来一个叫做azui的奇葩操作，我们把开着的灯看作数字1，把关着的灯看作数字0，定义 0 azui 0 = 1,0 azui 1 = 0,1 azui 1 = 1, 1 azui 0 = 0。现在小 A有 N个问题 azui(l,r)，表示询问从左往右的第 l个灯向右一个一个azui到第 r个灯的结果是什么。
输入
第1行一个整数N表示序列的长度。
第2行N个整数Ai，每个数不是0就是1，表示灯是关的还开的。
第3行一个整数M表示询问的个数。
第4~M+3行，每行两个整数l和r，表示询问azui(l,r)。
输出
共M行，第i行回答第i个询问。
样例数据
| 样例输入 | 样例输出 |
5 | 0 |
<数据范围>
对于30%的数据，N和M <= 5000
对于80%的数据，N和M <= 500000
对于100%的数据，N和M <= 1000000
解析
看到数据范围，就觉得这题肯定可以通过预处理来使单次查询变成O(1)的。(那些写线段树的着实把我吓了一跳。) 下面，我们来看一看思路：
通过一系列计算，我们可以发现这样一个结论，假设一个由0和1组成的串S通过azui运算得到的答案是1，那么我们若将S的第一个取反，那么答案同样会取反(其实修改任意一个数，这个结论都适用)。那么我们就可以这样搞：先对整个01串做一次azui运算，用数组azui[MAXN]记录每一个地方的运算中间值。在后面的查询操作中，我们只需要比较01串在l位置上的数和azui运算在这个位置上的中间值azui[l]，若相同，则最后的答案就是azui[r]，否则，就对azui[r]取反。
其实还有一个更简单的思路：
先用一个前缀和数组，记录01串中每一段的0的个数，对于查询azui(l,r)，若区间[l,r]的0的个数为奇数个，答案就是0；若为偶数个，答案就是1。
Code
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<iostream> #define MAXN 1000010 using namespace std; int Light[MAXN];
int cal[MAXN]; int azui(int a,int b)
{
if(a==b)
return ;
return ;
} int ops(int a)
{
if(a==)
return ;
return ;
} int main()
{int num;
scanf("%d",&num);
for(int i=;i<=num;i++)
{
scanf("%d",&Light[i]);
}
cal[]=Light[];
for(int i=;i<=num;i++)
{
cal[i]=azui(Light[i],cal[i-]);
}
int q_num;
scanf("%d",&q_num);
for(int i=;i<=q_num;i++)
{
int l,r;
scanf("%d%d",&l,&r);
if(cal[l]==Light[l])
{
printf("%d\n",cal[r]);
}
else
{
printf("%d\n",ops(cal[r]));
}
}
return ;
}
小G的烦恼 (meizi)
题目描述
小 G 最近郁闷死了，MZ 想考考他的智商，给了他一道题，但是小G 退役了这么久，怎么可能做的出来啊？于是他跑去向 quack 大神求助，可是 quack 大神要打牌，于是找到了你，希望能够不让 MZ 失望。
问题是这样的：MZ 想去全球各地旅行。原本是有两家航空公司可以选择的，但是现在那两家公司合并了。然而，在合并初期，两家还没有交接好，于是出现了两家都要收钱的问题。由于 MZ 只想出去玩一个月，她可以选择包月机票（两家公司都有），对于其中的一家公司 A 来说，只要花费 X 元，即可以在持有另一家公司的合法包月机票的情况下，乘坐任何票价不高于 A 公司定价的 X 元的飞机。另一家公司也是一样的。
简单来说，对于航线 i 有 2 种价格 Pi 和 Qi，分别是 A 公司和 B 公司的定价。假设你持有 X 元的 A 公司月票和 Y 元的 B 公司月票，当Pi<=X 并且 Qi<=Y 时，你才可以乘坐航线 i。当然，如果单独购买这一趟航班的两张票也是可以的。
现在 MZ 告诉你了 N-1 个她想要去的城市，MZ 初始时在 1 号位置，并且告诉了你所有航线的两个价格。想要知道，最小的花费。
输入
第 1 行 2 个整数 N、M 分别表示城市的个数，航线的条数。
第 2-M+1 行，每行 4 个整数 ui，vi，Pi，Qi，分别表示航线的两个城市(飞机可以来回开)，和两种价格。(可能存在重边和自环)
输出
共一行，一个整数 ANS，表示最小的花费。
样例数据
| 样例输入 | 样例输出 |
5 5 | 7 |
<样例解释>
选择除了 2-4 的所有边，所以答案是 3+4=7。
<数据范围>
对于20%的数据 N,M <= 15
对于50%的数据 N <= 200, M <= 500
对于80%的数据 N <= 500, M <= 1000
对于100%的数据 N <= 2000, M <= 5000, Pi, Qi <= 10^9
解析
我们会发现，在不下降地枚举了一个月票的价格之后，另外一张月票的价格是单调不上升的。我们就可以用一个指针来单调不上升的枚举另一张月票的价格。然后BFS(DFS)来判断图是否连通就可以了！
Code
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream> #define MAXN 200010
#define MAXM 500010 using namespace std; struct Edge
{
int v,a,b,nxt;
}e[MAXM<<]; int Adj[MAXN],cnt; inline void Add(int u,int v,int a,int b)
{
e[++cnt].v=v;
e[cnt].a=a;
e[cnt].b=b;
e[cnt].nxt=Adj[u];
Adj[u]=cnt;
} int a[MAXN],b[MAXN];
int n,m,mx1,mx2,ans=0x7f7f7f7f; bool BFS()
{
int q[MAXN],l,r,u;
bool v[MAXN];
l=r=;
q[++r]=;
for(int i=;i<=n;++i)
v[i]=;
v[]=;
while(l<r)
{
u=q[++l];
for(int i=Adj[u];i;i=e[i].nxt)
if(!v[e[i].v]&&e[i].a<=mx1&&e[i].b<=mx2)
{
q[++r]=e[i].v;
v[e[i].v]=;
}
}
if(r!=n)
return ;
ans=min(ans,mx1+mx2);
return ;
} int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(int i=;i<=m;++i)
{
scanf("%d%d%d%d",&u,&v,a+i,b+i);
Add(u,v,a[i],b[i]);
Add(v,u,a[i],b[i]);
}
sort(a+,a+m+);
sort(b+,b+m+);
int l,r,mid;
mx2=b[m];
for(int i=n-;i<=m;++i)
{
mx1=a[i];
l=n-;
r=m;
while(l<=r)
{
mid=(l+r)>>;
mx2=b[mid];
if(BFS())
{
ans=min(ans,mx1+mx2);
r=mid-;
}
else
l=mid+;
}
}
printf("%d",ans);
return ;
}
小Q的新玩具 (toy)
题目描述
期末考试完了，小 Q 得到了一件套新玩具，总共有 N 个零件。现在小 Q 想把新玩具搬回家里，可是他遇到了新的问题：每个零件有自己的重量 Wi ，小 Q 要租车把它们带回家。车每次只能运总重量和小于 Lim 的玩具，按照其中最重的玩具的重量收费。零件不能拆分成更小的部分。为了不打乱零件的顺序，增加自己
拼装的难度，每次装车只能装连续的部分。
输入
第一行两个整数 N 和 Limit。
接下来的 N 行，每行一个整数，代表第 i 个零件的重量。
输出
输出最少的花费。
样例数据
| 样例输入 | 样例输出 |
8 17 | 12 |
<数据范围>
对于 30%的数据，N <= 1000
对于 100%的数据，N <= 300000
数据保证Wi以及Limit均在int范围之内。
解析
我们考虑决策点，假如当前正在选择 f[i]的决策点。然后对于每个 i 来说，转移点 j向左移动时，max[j+1,i]单调不递减。所以我们看可以维护一个决策点的队列，满足区间和不大于 lim 且 Wq1 >Wq2 >…>Wqi 且队列 q 中包含所有满足上述条件的决策点,那么，从这里面的决策点一定有最优的决策点。
考虑到原来 NOIP2012 开车旅行里用到了 set，我们维护决策点也可以用 set，当然线段树也是可以的。其实我们就是需要一个数据结构支持插入，删除和取最小值。
Code
#include<cstdio>
#include<algorithm> #define ll long long using namespace std; int n,lim;
ll s[],mx[],f[]; void build(int x,int l,int r)
{
if(l==r)
{
mx[x]=s[l]-s[l-];
return;
}
build(x<<,l,(l+r)>>);
build(x<<|,((l+r)>>)+,r);
mx[x]=max(mx[x<<],mx[x<<|]);
} ll query(int x,int l,int r,int L,int R)
{
if(l==L&&r==R)
return mx[x];
int mid=(l+r)>>;
if(R<=mid)
return query(x<<,l,mid,L,R);
if(L>mid)
return query(x<<|,mid+,r,L,R);
return max(query(x<<,l,mid,L,mid),query(x<<|,mid+,r,mid+,R));
}
int main()
{
scanf("%d%d",&n,&lim);
for(int i=;i<=n;++i)
scanf("%I64d",&s[i]),s[i]+=s[i-];
build(,,n);
for(int i=;i<=n;++i)
{
ll mi=1ll<<;
for(int j=i-;~j;--j)
{
if(s[i]-s[j]>lim)
break;
mi=min(mi,f[j]+query(,,n,j+,i));
}
f[i]=mi;
}
printf("%I64d",f[n]);
return ;
}
Time: 2017-07-25