「CF241X」Bayan 2012 – 2013 Elimination Round(ACM ICPC Rules, English statements) - 模拟 - 深度搜索 - 差分约束

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define mod 1000000007
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,K,ans;
int c[1005],d[1005];
int main()
{
    n=read();K=read();
    for(int i=1;i<=n;i++)d[i]=read();
    for(int i=1;i<=n;i++)c[i]=read();
    int mx=0,now=0;
    for(int i=1;i<=n;i++)
    {
        mx=max(mx,c[i]);
        now+=c[i];
        while(now<d[i])now+=mx,ans+=K;
        ans+=d[i];now-=d[i];
    }
    printf("%d\n",ans);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define mod 1000000007

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char c=getchar();

while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

return x*f;

}

int n,K,ans;

int c[1005],d[1005];

int main()

{

n=read();K=read();

for(int i=1;i<=n;i++)d[i]=read();

for(int i=1;i<=n;i++)c[i]=read();

int mx=0,now=0;

for(int i=1;i<=n;i++)

{

mx=max(mx,c[i]);

now+=c[i];

while(now<d[i])now+=mx,ans+=K;

ans+=d[i];now-=d[i];

}

printf("%d\n",ans);

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,D;
int a[50005];
ll ans,m,num[35][2];
map<int,int>mp;
ll cal(int l1,int r1,int l2,int r2)
{
    ll sum=0;
    memset(num,0,sizeof(num));
    for(int i=l1;i<=r1;i++)
    {
        for(int d=0;d<=30;d++)
            num[d][(a[i]&(1<<d))>0]++;
    }
    for(int i=l2;i<=r2;i++)
    {
        for(int d=0;d<=30;d++)
            sum+=(num[d][((a[i]&(1<<d))>0)^1]<<d)%mod;
    }
    return sum%mod;
}
bool cmp(int a,int b)
{
    return (a>>D)<(b>>D);
}
void solve()
{
    int now=0;
    for(int d=30;d>=0;d--)
    {
        mp.clear();
        for(int i=1;i<=n;i++)
            mp[(a[i]>>d)<<d]++;
        ll sum=0;
        now|=1<<d;
        for(map<int,int>::iterator i=mp.begin();i!=mp.end();i++)
            sum+=(ll)i->second*mp[i->first^now];
        sum/=2;
        if(sum<=m)
        {
            if(sum)
            {
                m-=sum;
                ll tmp=0;
                for(map<int,int>::iterator i=mp.begin();i!=mp.end();i++)
                {
                    D=d;
                    pair<int*,int*>t1,t2;
                    t1=equal_range(a+1,a+n+1,i->first,cmp);
                    t2=equal_range(a+1,a+n+1,i->first^now,cmp);
                    tmp=(tmp+cal(t1.first-a,t1.second-a-1,t2.first-a,t2.second-a-1))%mod;
                }
                tmp%=mod;
                ans=(ans+tmp*(mod+1)/2)%mod;
            }
            now^=1<<d;
        }
    }
    cout<<(ans+now*m)%mod<<endl;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+n+1);
    solve();
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,D;

int a[50005];

ll ans,m,num[35][2];

map<int,int>mp;

ll cal(int l1,int r1,int l2,int r2)

{

ll sum=0;

memset(num,0,sizeof(num));

for(int i=l1;i<=r1;i++)

{

for(int d=0;d<=30;d++)

num[d][(a[i]&(1<<d))>0]++;

}

for(int i=l2;i<=r2;i++)

{

for(int d=0;d<=30;d++)

sum+=(num[d][((a[i]&(1<<d))>0)^1]<<d)%mod;

}

return sum%mod;

}

bool cmp(int a,int b)

{

return (a>>D)<(b>>D);

}

void solve()

{

int now=0;

for(int d=30;d>=0;d--)

{

mp.clear();

for(int i=1;i<=n;i++)

mp[(a[i]>>d)<<d]++;

ll sum=0;

now|=1<<d;

for(map<int,int>::iterator i=mp.begin();i!=mp.end();i++)

sum+=(ll)i->second*mp[i->first^now];

sum/=2;

if(sum<=m)

{

if(sum)

{

m-=sum;

ll tmp=0;

for(map<int,int>::iterator i=mp.begin();i!=mp.end();i++)

{

D=d;

pair<int*,int*>t1,t2;

t1=equal_range(a+1,a+n+1,i->first,cmp);

t2=equal_range(a+1,a+n+1,i->first^now,cmp);

tmp=(tmp+cal(t1.first-a,t1.second-a-1,t2.first-a,t2.second-a-1))%mod;

}

tmp%=mod;

ans=(ans+tmp*(mod+1)/2)%mod;

}

now^=1<<d;

}

cout<<(ans+now*m)%mod<<endl;

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)a[i]=read();

sort(a+1,a+n+1);

solve();

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int h1,h2,n,ans;
int l[105],r[105],w[105];
bool vis[105],typ[105];
void swap()
{
    for(int i=1;i<=n;i++)typ[i]^=1;
    h1=100-h1;h2=100-h2;
}
void solve(int T)
{
    memset(vis,0,sizeof(vis));
    int x=100000,y=(T-1)*100+h1;
    if(T&1)y+=h2;else y+=100-h2;
    int tot=0,f=1;
    double t=(double)x/y,nx=0;
    for(int i=1;i<=T;i++)
    {
        if(i==1)nx+=t*h1;
        else nx+=100*t;
        bool flag=0;
        for(int j=1;j<=n;j++)
            if(typ[j]==f&&l[j]<=nx&&nx<=r[j])
            {
                if(vis[j])return;
                vis[j]=1;tot+=w[j];
                flag=1;break;
            }
        f^=1;if(!flag)return;
    }
    ans=max(ans,tot);
}
int main()
{
    h1=read();h2=read();n=read();
    char c[2];
    for(int i=1;i<=n;i++)
    {
        w[i]=read();
        scanf("%s",c+1);
        l[i]=read();r[i]=read();
        typ[i]=(c[1]=='F');
    }
    for(int i=1;i<=n;i++)solve(i);
    swap();
    for(int i=1;i<=n;i++)solve(i);
    printf("%d\n",ans);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int h1,h2,n,ans;

int l[105],r[105],w[105];

bool vis[105],typ[105];

void swap()

{

for(int i=1;i<=n;i++)typ[i]^=1;

h1=100-h1;h2=100-h2;

}

void solve(int T)

{

memset(vis,0,sizeof(vis));

int x=100000,y=(T-1)*100+h1;

if(T&1)y+=h2;else y+=100-h2;

int tot=0,f=1;

double t=(double)x/y,nx=0;

for(int i=1;i<=T;i++)

{

if(i==1)nx+=t*h1;

else nx+=100*t;

bool flag=0;

for(int j=1;j<=n;j++)

if(typ[j]==f&&l[j]<=nx&&nx<=r[j])

{

if(vis[j])return;

vis[j]=1;tot+=w[j];

flag=1;break;

}

f^=1;if(!flag)return;

}

ans=max(ans,tot);

}

int main()

{

h1=read();h2=read();n=read();

char c[2];

for(int i=1;i<=n;i++)

{

w[i]=read();

scanf("%s",c+1);

l[i]=read();r[i]=read();

typ[i]=(c[1]=='F');

}

for(int i=1;i<=n;i++)solve(i);

swap();

for(int i=1;i<=n;i++)solve(i);

printf("%d\n",ans);

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool flag;
int n,p,tot;
int a[30],pos[30];
bool mark[30];
void dfs(int x,int k,int xo,int mo)
{
	if(flag)return;
	if(x==tot+1)
	{
		if(xo==0&&mo==0&&k!=1)
		{
			puts("Yes");
			flag=1;
			printf("%d\n",k-1);
			for(int i=1;i<=tot;i++)
				if(mark[i])printf("%d ",pos[i]);
		}		
		return;
	}
	dfs(x+1,k,xo,mo);
	if(a[x]<10)mo=mo*10+a[x];
	else mo=mo*100+a[x];
	mo%=p;
	mark[x]=1;dfs(x+1,k+1,xo^a[x],mo);mark[x]=0;
}
int main()
{
	n=read();p=read();
	int x;
	for(int i=1;i<=n;i++)
	{
		x=read();
		if(x<=25)a[++tot]=x,pos[tot]=i;
	}
	dfs(1,1,0,0);
	if(!flag)puts("No");
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

bool flag;

int n,p,tot;

int a[30],pos[30];

bool mark[30];

void dfs(int x,int k,int xo,int mo)

{

if(flag)return;

if(x==tot+1)

{

if(xo==0&&mo==0&&k!=1)

{

puts("Yes");

flag=1;

printf("%d\n",k-1);

for(int i=1;i<=tot;i++)

if(mark[i])printf("%d ",pos[i]);

}

return;

}

dfs(x+1,k,xo,mo);

if(a[x]<10)mo=mo*10+a[x];

else mo=mo*100+a[x];

mo%=p;

mark[x]=1;dfs(x+1,k+1,xo^a[x],mo);mark[x]=0;

}

int main()

{

n=read();p=read();

int x;

for(int i=1;i<=n;i++)

{

x=read();

if(x<=25)a[++tot]=x,pos[tot]=i;

}

dfs(1,1,0,0);

if(!flag)puts("No");

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt;
int last[1005],dis[1005],T[1005];
int u[5005],v[5005];
bool mark[1005],vis[1005];
struct edge{
    int to,next,v;
}e[10005];
void insert(int u,int v,int w)
{
    e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
}
void dfs(int x)
{
    vis[x]=1;
    if(x==n)
    {
        mark[x]=1;return;
    }
    for(int i=last[x];i;i=e[i].next)
        if(e[i].v>0)
        {
            if(!vis[e[i].to])dfs(e[i].to);
            if(mark[e[i].to])mark[x]=1;
        }
}
void spfa()
{
    queue<int>q;
    q.push(1);
    memset(vis,0,sizeof(vis));vis[1]=0;
    memset(dis,127,sizeof(dis));dis[1]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();vis[x]=0;
        for(int i=last[x];i;i=e[i].next)
            if(dis[x]+e[i].v<dis[e[i].to]&&mark[e[i].to])
            {
                dis[e[i].to]=dis[x]+e[i].v;
                if(!vis[e[i].to])
                {
                    q.push(e[i].to);
                    T[e[i].to]++;
                    if(T[e[i].to]>n){puts("No");return;}                    
                }
                vis[e[i].to]=1;
            }
    }
    puts("Yes");
    for(int i=1;i<=m;i++)
        if(dis[u[i]]-dis[v[i]]==-1)puts("1");
        else puts("2");
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        u[i]=read();v[i]=read();
        insert(u[i],v[i],2);insert(v[i],u[i],-1);       
    } 
    dfs(1);
    spfa();
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt;

int last[1005],dis[1005],T[1005];

int u[5005],v[5005];

bool mark[1005],vis[1005];

struct edge{

int to,next,v;

}e[10005];

void insert(int u,int v,int w)

{

e[++cnt]=(edge){v,last[u],w};last[u]=cnt;

}

void dfs(int x)

{

vis[x]=1;

if(x==n)

{

mark[x]=1;return;

}

for(int i=last[x];i;i=e[i].next)

if(e[i].v>0)

{

if(!vis[e[i].to])dfs(e[i].to);

if(mark[e[i].to])mark[x]=1;

}

void spfa()

{

queue<int>q;

q.push(1);

memset(vis,0,sizeof(vis));vis[1]=0;

memset(dis,127,sizeof(dis));dis[1]=0;

while(!q.empty())

{

int x=q.front();q.pop();vis[x]=0;

for(int i=last[x];i;i=e[i].next)

if(dis[x]+e[i].v<dis[e[i].to]&&mark[e[i].to])

{

dis[e[i].to]=dis[x]+e[i].v;

if(!vis[e[i].to])

{

q.push(e[i].to);

T[e[i].to]++;

if(T[e[i].to]>n){puts("No");return;}

}

vis[e[i].to]=1;

}

puts("Yes");

for(int i=1;i<=m;i++)

if(dis[u[i]]-dis[v[i]]==-1)puts("1");

else puts("2");

}

int main()

{

n=read();m=read();

for(int i=1;i<=m;i++)

{

u[i]=read();v[i]=read();

insert(u[i],v[i],2);insert(v[i],u[i],-1);

}

dfs(1);

spfa();

return 0;

}

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,K,X,Y;
int x[30],y[30],b[105][105];
int nx[1005],ny[1005];
char a[105][105],ch[1005];
int main()
{
    n=read();m=read();K=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a[i]+1);
        for(int j=1;j<=m;j++)
            if(a[i][j]>='a'&&a[i][j]<='z')
                x[a[i][j]-'a']=i,y[a[i][j]-'a']=j,b[i][j]=1;
            else b[i][j]=a[i][j]-'0';
    }
    X=read();Y=read();
    scanf("%s",ch+1);
    int l=strlen(ch+1);
    for(int i=1;i<=l;i++)
        nx[i]=x[ch[i]-'a'],ny[i]=y[ch[i]-'a'];
    nx[++l]=read();ny[l]=read();
    for(int i=1;i<=l&&K>0;i++)
        while(X!=nx[i]||Y!=ny[i])
        {
            K-=b[X][Y];
            if(K<0)break;
            if(X>nx[i])X--;
            if(X<nx[i])X++;
            if(Y>ny[i])Y--;
            if(Y<ny[i])Y++;
        }
    printf("%d %d\n",X,Y);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,K,X,Y;

int x[30],y[30],b[105][105];

int nx[1005],ny[1005];

char a[105][105],ch[1005];

int main()

{

n=read();m=read();K=read();

for(int i=1;i<=n;i++)

{

scanf("%s",a[i]+1);

for(int j=1;j<=m;j++)

if(a[i][j]>='a'&&a[i][j]<='z')

x[a[i][j]-'a']=i,y[a[i][j]-'a']=j,b[i][j]=1;

else b[i][j]=a[i][j]-'0';

}

X=read();Y=read();

scanf("%s",ch+1);

int l=strlen(ch+1);

for(int i=1;i<=l;i++)

nx[i]=x[ch[i]-'a'],ny[i]=y[ch[i]-'a'];

nx[++l]=read();ny[l]=read();

for(int i=1;i<=l&&K>0;i++)

while(X!=nx[i]||Y!=ny[i])

{

K-=b[X][Y];

if(K<0)break;

if(X>nx[i])X--;

if(X<nx[i])X++;

if(Y>ny[i])Y--;

if(Y<ny[i])Y++;

}

printf("%d %d\n",X,Y);

return 0;

}

hzwer.com _ Home | http://hzwer.com

「CF241X」Bayan 2012 – 2013 Elimination Round(ACM ICPC Rules, English statements)

分类目录

热门文章

Myfriends

近期评论