2012-2013 ACM-ICPC Northeastern European Regional Contest (NEERC 12)

Problems

#	Name
A	Addictive Bubbles¹ addictive.in / addictive.out 2 s, 256 MB	x438
B	Blind Problem Solving¹ standard input/output 2 s, 256 MB	x124
C	Caravan Robbers¹ caravan.in / caravan.out 2 s, 256 MB	x178
D	Disjoint Regular Expressions¹ disjoint.in / disjoint.out 2 s, 256 MB	x34
E	Exact Measurement¹ exact.in / exact.out 2 s, 256 MB	x220
F	Folding Snake Cube¹ folding.in / folding.out 2 s, 256 MB	x76
G	Great Deceiver¹ great.in / great.out 2 s, 256 MB	x359
H	Hyperdrome¹ hyperdrome.in / hyperdrome.out 2 s, 256 MB	x268
I	Identification of Protein¹ identification.in / identification.out 2 s, 256 MB	x29
J	Jumping Around¹ jumping.in / jumping.out 2 s, 256 MB	x95
K	Kingdom Reunion¹ kingdom.in / kingdom.out 2 s, 256 MB
L	Labyrinth of the Minotaur¹ labyrinth.in / labyrinth.out 2 s, 256 MB	x53

A.构造，水题。

 #include <map>

 #include <set>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <climits>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef double DB;

 typedef long long ll;

 typedef pair<int, int> PII;

 #define pb push_back

 #define MP make_pair

 #define lson l, m, rt << 1

 #define rson m + 1, r, rt << 1 | 1

 #define re freopen("addictive.in", "r", stdin)

 #define we freopen("addictive.out", "w", stdout)

 #define FOR(i,x,y) for(i=x;i<=y;i++)

 #define FORD(i,x,y) for(i=x;

 #define REP(i,x) for(i=0;i<x;i++)

 #define mf1(x) memset(x,-1,sizeof(x))

 #define mz(x) memset(x,0,sizeof(x))

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 const int maxn=;

 const int maxm=;

 const int INF=;

 int h,w,c;

 int a[maxn];

 int an[maxn][maxn];

 void farm(){

     int i,j,k,l,m;

     k=;

     j=;

     l=;

     mz(an);

     REP(i,h){

         REP(m,w){

             while(a[l]==)l++;

             an[i][j]=l;

             a[l]--;

             j+=k;

         }

         j-=k;

         k=-k;

     }

 }

 int main(){

     re;

     we;

     int i,j;

     while(RD3(h,w,c)!=EOF){

         FOR(i,,c)scanf("%d",&a[i]);

         farm();

         REP(i,h){

             REP(j,w)printf("%d",an[i][j]);

             puts("");

         }

     }

 }

C.long double二分答案，最后枚举分母找一个分子。

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("caravan.in","r",stdin)

 #define WE  freopen("caravan.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const LD pi=acos(-1.0);

 const LD eps=1e-;

 const int maxn=;

 struct qj{

     int l,r;

 }a[maxn];

 bool cmp(qj x, qj y){

     return x.l < y.l;

 }

 int n;

 int ans0,ans1;

 bool ok(LD x){

     int i;

     LD y=0.0;

     REP(i,n){

         if(a[i].r - x + eps < y)return ;

         y = max((LD)a[i].l , y) + x;

     }

     return ;

 }

 void farm(){

     int i;

     LD l=0.0,r=10000000.0,mid;

     REP(i,n)r=min(r , (LD)(a[i].r-a[i].l));

     sort(a,a+n,cmp);

     while(r-l>eps){

         mid=(l+r)*0.5;

         if(ok(mid))l=mid;

         else r=mid;

     }

     LD dou=1.0;

     FOR(i,,){

         if( fabs(r*i - (LD)ceil(r*i))<dou){

             ans0=ceil(r*i);

             ans1=i;

             dou=fabs(r*i - (LD)ceil(r*i));

         }

         if( fabs(r*i - (LD)floor(r*i))<dou){

             ans0=floor(r*i);

             ans1=i;

             dou=fabs(r*i - (LD)floor(r*i));

         }

     }

 }

 int main(){

     RE;

     WE;

     int i;

     while(scanf("%d",&n)!=EOF){

         REP(i,n)RD2(a[i].l, a[i].r);

         farm();

         printf("%d/%d\n",ans0,ans1);

     }

 }

E.贪心，分成19种包，分别按大小排序，要取其中一种肯定是取那种最大的。每次取能处理最低的非零位的最重的包，让它产生尽量多的零。

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define mz(array) memset(array, 0, sizeof(array))

 #define mf1(array) memset(array, -1, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(i=0;i<(n);i++)

 #define FOR(i,x,n) for(i=(x);i<=(n);i++)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("exact.in","r",stdin)

 #define WE  freopen("exact.out","w",stdout)

 #define mp make_pair

 #define pb push_back

 #define pf push_front

 #define ppf pop_front

 #define ppb pop_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef long double LD;

 const LD pi=acos(-1.0);

 const LD eps=1e-;

 ll X;

 int n;

 struct Box {

     ll n;

     int i;

     Box(int _i,ll _n) {

         i=_i;

         n=_n;

     }

 };

 bool cmp(Box x, Box y) {

     return x.n<y.n;

 }

 ll ten[];

 vector<Box>a[];

 vector<int>an;

 bool farm() {

     int i,j,k;

     REP(i,)sort(a[i].begin(),a[i].end(),cmp);

     an.clear();

     ll x=X;

     ll t=;

     k=;

     while(x) {

         while(k<= && x%ten[k+]==)k++;

         int mai=-;

         ll ma=;

         //printf("x=%I64d , k=%d\n",x,k);

         FOR(i,,k) {

             if(!a[i].empty()) {

                 if(a[i].back().n * ten[i] >ma) {

                     mai=i;

                     ma=a[i].back().n * ten[i];

                 }

             }

         }

         if(mai==-)return ;

         an.pb(a[mai].back().i);

         t += a[mai].back().n * ten[mai];

         //printf("t=%I64d\n",t);

         ll q;

         if(x>t){

             j=k;

             while(x%ten[j+] <= t)j++;

             if(j!=k)q=x%ten[j];

             else q=t;

         }else q=x;

         x-=q;

         t-=q;

         a[mai].pop_back();

     }

     return ;

 }

 void init() {

     int i;

     ten[]=;

     FOR(i,,) {

         ten[i]=ten[i-]*;

     }

     ten[]=*ten[];

 }

 int main() {

     RE;

     WE;

     init();

     int i,x;

     ll y;

     while(scanf("%I64d%d",&X,&n)!=EOF) {

         REP(i,)a[i].clear();

         FOR(i,,n) {

             scanf("%d%I64d",&x,&y);

             a[x].pb(Box(i,y));

         }

         if(farm()) {

             printf("%d\n",an.size());

             if(!an.empty())printf("%d",an[]);

             FOR(i,,an.size()-)printf(" %d",an[i]);

             puts("");

         } else puts("-1");

     }

     return ;

 }

G.数位DP，写简单点就是记忆化搜索型的。

 #include <map>

 #include <set>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <climits>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef double DB;

 typedef long long ll;

 typedef pair<int, int> PII;

 #define pb push_back

 #define MP make_pair

 #define lson l, m, rt << 1

 #define rson m + 1, r, rt << 1 | 1

 #define RE freopen("great.in", "r", stdin)

 #define WE freopen("great.out", "w", stdout)

 #define FOR(i,x,y) for(i=x;i<=y;i++)

 #define FORD(i,x,y) for(i=x;

 #define REP(i,x) for(i=0;i<x;i++)

 #define mf1(x) memset(x,-1,sizeof(x))

 #define mz(x) memset(x,0,sizeof(x))

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 const int maxn=;

 const int maxm=;

 const int INF=;

 ll n;

 int k;

 ll pow(int x){

     int i;

     ll re=;

     REP(i,x)re*=k;

     return re;

 }

 int a[maxn];

 ll f[maxn];

 ll dfs(int w, bool limit){

     if(w<) return ;

     if(!limit && f[w]!=-)return f[w];

     int maxi=limit?a[w]:k-;

     if(w%==)maxi=;

     ll re=;

     int i;

     FOR(i,,maxi){

         re+=dfs(w-, limit && i==a[w]);

     }

     if(!limit)f[w]=re;

     return re;

 }

 ll farm(){

     ll re=;

     ll t=n;

     ll w=;

     ll m=;

     int i,j;

     while(t){

         a[w]=t%k;

         t/=k;

         w++;

     }

     mf1(f);

     return dfs(w-, );

 }

 int main(){

     RE;

     WE;

     int i,j;

     while(scanf("%I64d%d",&n,&k)!=EOF){

         printf("%I64d\n",farm());

     }

 }

H.状压。1~i中各个字母是奇数个还是偶数个，能用2^52种状态表示。状态R xor 状态L，得到的就是区间[L,R]的状态，其中有0个或1个1就是可行的。

用hash存之前出现过的状态，枚举那个唯一的一个1来统计，O(52n)这样。

 #include <map>

 #include <set>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <climits>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <hash_map>

 using namespace std;

 using namespace stdext;

 typedef double DB;

 typedef long long ll;

 typedef unsigned int usint;

 typedef pair<int, int> PII;

 #define pb push_back

 #define MP make_pair

 #define lson l, m, rt << 1

 #define rson m + 1, r, rt << 1 | 1

 #define RE freopen("hyperdrome.in", "r", stdin)

 #define WE freopen("hyperdrome.out", "w", stdout)

 #define FOR(i,x,y) for(i=x;i<=y;i++)

 #define FORD(i,x,y) for(i=x;

 #define REP(i,x) for(i=0;i<x;i++)

 #define mf1(x) memset(x,-1,sizeof(x))

 #define mz(x) memset(x,0,sizeof(x))

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 const int maxn=;

 const int maxm=;

 const int INF=;

 char s[maxn];

 int q[];

 int n;

 ll l[];

 //hash_map<ll,ll>S;

 const ll NONE=-;

 class hash {

 public:

     hash() {

         memset(a,0xff,sizeof(a));

     }

     usint locate(ll x) {

         usint l=x%MOD;

         while(a[l]!=x&&a[l]!=NONE) l=l+;

         return l;

     }

     void insert(ll x,ll va) {

         usint l=locate(x);

         if(a[l]==NONE) {

             a[l]=x;

             v[l]=va;

         }

     }

     void add(ll x) {

         usint l=locate(x);

         if(a[l]==NONE) {

             a[l]=x;

             v[l]=;

         }else{

             v[l]++;

         }

     }

     ll find(ll x) {

         usint l=locate(x);

         return a[l]==x?v[l]:;

     }

     void clear() {

         memset(a,-,sizeof(a));

     }

 private:

     static const usint MOD=;

     ll a[MOD+];

     usint v[MOD+];

 } S;

 ll farm(){

     int i,j;

     ll x=;

     ll re=;

     S.clear();

     S.insert(,);

     REP(i,n){

         x^=(l[q[s[i]]]);

         FOR(j,,){

             re+=S.find(x ^ l[j]);

         }

         re+=S.find(x);

         S.add(x);

         //printf("%I64d,%I64d,%I64d,%I64d\n",x,S[x],re,1LL<<q[s[i]]);

     }

     return re;

 }

 void init(){

     int i;

     FOR(i,'a','z')q[i]=i-'a';

     FOR(i,'A','Z')q[i]=i-'A'+;

     FOR(i,,)l[i]=1LL<<i;

 }

 int main(){

     RE;

     WE;

     int i,j;

     init();

     while(scanf("%d",&n)!=EOF){

         scanf(" %s",s);

         printf("%I64d\n",farm());

     }

 }

秒客网

2012-2013 ACM-ICPC Northeastern European Regional Contest (NEERC 12)

相关文章