@KirinBill
2017-10-09T15:10:42.000000Z
字数 4784
阅读 1149
题解
套题
不要急,慢慢来。
目录
#include <cstdio>
#include <utility>
#define x first
#define y second
using std::pair;
typedef pair<int,int> position;
const int MAXN=4e5+5;
int n;
char cmd[MAXN];
namespace solve1
{
inline int operate(int l){
position pos(0,0);
int ret=0;
for(;l<=n;++l){
switch(cmd[l]){
case 'U': ++pos.y; break;
case 'D': --pos.y; break;
case 'L': --pos.x; break;
case 'R': ++pos.x; break;
}
if(pos.x==0 && pos.y==0) ++ret;
}
return ret;
}
inline int solve(){
int ret=0;
for(int i=1;i<=n;++i)
ret+=operate(i);
return ret;
}
}
namespace solve2
{
int arr[MAXN<<1];
inline long long solve(){
long long ret=0;
int *sum=&arr[n+1];
sum[0]=1;
for(int i=1,tmp=0;i<=n;++i){
cmd[i]=='L' ? --tmp:++tmp;
ret+=sum[tmp];
++sum[tmp];
}
return ret;
}
}
int main(){
freopen("command.in","r",stdin);
freopen("command.out","w",stdout);
scanf("%d%s",&n,cmd+1);
if(n<=4000) printf("%d",solve1::solve());
else printf("%lld",solve2::solve());
return 0;
}
vector
中,对于询问算一下即可。
#include <cstdio>
#include <vector>
using std::vector;
const int MAXN=1e5+5;
int n,q,tot,idx;
int he[MAXN],up_pos[MAXN],dwn_pos[MAXN],pos[MAXN][2];
bool vis[MAXN];
vector<int> cir[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
inline void addE(int u,int v){
static int cnt=0;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
inline void build(){
for(int i=1;i<=n;++i)
addE(dwn_pos[i],up_pos[i]);
}
void find_cir(int u){
cir[tot].push_back(u);
pos[u][0]=tot,pos[u][1]=++idx;
vis[u]=true;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(!vis[v]) find_cir(v);
}
}
int main(){
freopen("position.in","r",stdin);
freopen("position.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1,u,d;i<=n;++i){
scanf("%d%d",&u,&d);
up_pos[u]=i;
dwn_pos[d]=i;
}
build();
for(int i=1;i<=n;++i){
if(!vis[i]){
++tot,idx=0;
find_cir(i);
}
}
for(int i=1,k,s;i<=q;++i){
scanf("%d%d",&k,&s);
printf("%d\n",cir[pos[k][0]][(pos[k][1]+s-1)%cir[pos[k][0]].size()]);
}
return 0;
}
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using std::max;
using std::queue;
const int MAXN=3005;
int n,m,s1,t1,l1,s2,t2,l2;
int he[MAXN],G[MAXN][MAXN];
struct line{int to,nex;}ed[MAXN<<1];
inline void addE(int u,int v){
static int cnt=0;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
inline void BFS(int s){
static bool vis[MAXN];
static queue<int> que;
memset(vis,false,sizeof(vis));
que.push(s);
vis[s]=true;
int u;
int *dis=G[s];
while(que.size()){
u=que.front();
que.pop();
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(!vis[v]){
dis[v]=dis[u]+1;
que.push(v);
vis[v]=true;
}
}
}
}
inline void cal_APSP(){
memset(G,30,sizeof(G));
for(int i=1;i<=n;++i){
G[i][i]=0;
BFS(i);
}
}
inline int solve(){
if(G[s1][t1]>l1 || G[s2][t2]>l2) return -1;
int ret=m-G[s1][t1]-G[s2][t2];
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(G[s1][i]+G[i][j]+G[j][t1]<=l1 && G[s2][i]+G[i][j]+G[j][t2]<=l2)
ret=max(ret,m-G[s1][i]-G[s2][i]-G[i][j]-G[j][t1]-G[j][t2]);
if(G[s1][i]+G[i][j]+G[j][t1]<=l1 && G[s2][j]+G[j][i]+G[i][t2]<=l2)
ret=max(ret,m-G[s1][i]-G[s2][j]-G[i][j]-G[j][t1]-G[i][t2]);
}
}
return ret;
}
int main(){
freopen("destroy.in","r",stdin);
freopen("destroy.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
addE(u,v),addE(v,u);
}
scanf("%d%d%d",&s1,&t1,&l1);
scanf("%d%d%d",&s2,&t2,&l2);
cal_APSP();
printf("%d",solve());
return 0;
}
#include <cstdio>
#include <algorithm>
using std::sort;
const int MAXN=200005;
int n,m;
struct day{
int t,id;
friend bool operator< (const day &a,const day &b){
return a.t<b.t;
}
}d[MAXN];
struct work{
int d,r,time,id;
static bool cmp_d(const work &a,const work &b){return a.d<b.d;}
static bool cmp_id(const work &a,const work &b){return a.id<b.id;}
}wk[MAXN];
template<typename type>
class BIT{
private:
type c[MAXN];
int lowbit(int x){return x&-x;}
public:
void add(int l,type val){
for(;l<=m;l+=lowbit(l))
c[l]+=val;
}
type qry(int r){
type ret=0;
for(;r;r-=lowbit(r))
ret+=c[r];
return ret;
}
};
BIT<int> cnt;
BIT<long long> ta;
inline void cal_time(work &now,int id){
static int cur=1;
for(;d[cur].t<=now.d && cur<=m;++cur){
ta.add(d[cur].id,-d[cur].t);
cnt.add(d[cur].id,-1);
}
long long sum=ta.qry(m)-(long long)now.d*cnt.qry(m);
if(now.r>sum){
now.time=0;
return;
}
int l=1,r=m,mid;
while(l<=r){
mid=l+r>>1;
if(now.r<=ta.qry(mid)-(long long)now.d*cnt.qry(mid))
r=mid-1;
else l=mid+1;
}
now.time=l;
}
int main(){
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d",&d[i].t);
ta.add(i,d[i].t);
cnt.add(i,1);
d[i].id=i;
}
sort(d+1,d+m+1);
for(int i=1;i<=n;++i){
scanf("%d%d",&wk[i].d,&wk[i].r);
wk[i].id=i;
}
sort(wk+1,wk+n+1,work::cmp_d);
for(int i=1;i<=n;++i)
cal_time(wk[i],i);
sort(wk+1,wk+n+1,work::cmp_id);
for(int i=1;i<=n;++i)
printf("%d ",wk[i].time);
return 0;
}