现在的位置: 首页 > 综合 > 正文

2012 ACM/ICPC 长春赛区网络赛

2013年12月01日 ⁄ 综合 ⁄ 共 4871字 ⁄ 字号 评论关闭

1001  A Simple Problem with Integers

参考地址:http://www.haogongju.net/art/1637871

题意:有两种操作,一种是更新区间a~b中 a <= i <= b and (i - a) % k == 0 的点加上c , 一种是询问Aa 的value

思路:明显的线段树 , 但是依然跪倒啊、、、cnt[i][k] = c 代表当前区间i 每隔k个字符累加c, 然后就是更新,如果存在要更新的区间那么直接更新就行,否则左孩子依旧更新,右孩子找到第一个属于a~b区间并且满足(i - a)%k==0 的点,继续更新,询问的时候要把 所有cnt[i][k] = c的影响算进去

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define lson l , m , rt<<1
#define rson m + 1 , r , rt<<1|1
const int maxn = 50005;
typedef long long ll;
ll cnt[50005*3][11];   //cnt[i][k]=c当前区间i每隔k个字符累加c
ll a[maxn];
void build(int l , int r , int rt) {
    int i;
    for(i = 1 ; i <= 10 ; i ++)
    cnt[rt][i] = 0;
    if(l == r) return;
    int m;
    m = (l + r) >> 1;
    build(lson);
    build(rson);    
}
void update(int l , int r , int rt , int L , int R , int k , ll c) {
    //printf("%d %d %d , %d %d %d %d\n",l,r,rt,L,R,k,c);
    //system("pause");
    if(L > R) return;
    if(l == L && r == R) {
        //printf("~~!");
        cnt[rt][k] += c;
        return;    
    }
    int m;
    m = (l + r) >> 1;
    if(m >= R) {
        update(lson , L , R , k , c);    
    } else if(m < L) {
        update(rson , L , R , k , c);    
    } else {
        update(lson , L , m , k , c);
        int st = (k - (m + 1 - L)%k)%k; 
        //printf("st = %d\n",st);
        update(rson , m + 1 + st , R , k , c);   
    }
}
ll query(int l , int r , int rt , int pos) {
    //printf("%d %d %d\n",l,r,rt);
    ll ans = 0;
    for(int i = 1 ; i <= 10 ; i ++) {
        if((pos - l)%i == 0) 
        ans += cnt[rt][i];    
    }
    if(l == r) return ans;
    int m = (l + r) >> 1; 
    if(pos <= m) return query(lson , pos) + ans;
    else return query(rson , pos) + ans;     
}
int main() {
    int  i , l , r , k , n , m , pos , op;
    ll c;
    while(~scanf("%d",&n)) {
        for(i = 1 ; i <= n ; i ++)
        scanf("%lld",&a[i]);
        scanf("%d",&m);
        build(1 , n , 1);
        while(m --) {
            scanf("%d",&op);
            if(op == 2) {
                scanf("%d",&pos);
                printf("%lld\n",a[pos]+query(1 , n , 1 , pos));    
            } else {
                scanf("%d %d %d %lld",&l,&r,&k,&c);
                update(1 , n , 1 , l , r , k , c);    
            }
        }
    }    
}

1002 Alice and Bob

题意:看到题目不要以为是博弈、、、 呵呵 , 是贪心、、、就是Alice有一些矩形,已知他们的长宽,Bob同样也有,求Alice最大可能覆盖Bob的矩形的个数(长宽都分别比塔大)

思路:具体参考 信息平台站的题解 http://acmicpc.info/  就是先把两个人的矩形按照h 、 w 进行排序,然后根据Alice的h去找满足能覆盖Bob的h然后在这些Bob的矩形中,找出Bob矩形的w刚好小于等于Alice的w的矩形,这是比较理想的一次覆盖,因为要留下较小的给其他矩形覆盖留更多的选择余地。这里用Muliset来搞。

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#define ft first
#define sd second
using namespace std;
const int maxn = 100010;
typedef pair<int , int> pii;
pii a[maxn] , b[maxn];
int main() {
    int T , n , i , j;
    scanf("%d",&T);
    while(T --) {
        scanf("%d",&n);
        for(i = 0 ; i < n ; i ++) scanf("%d%d",&a[i].ft,&a[i].sd);
        for(i = 0 ; i < n ; i ++) scanf("%d%d",&b[i].ft,&b[i].sd);
        sort(a , a + n);
        sort(b , b + n);
        multiset<int> mt;
        multiset<int>::iterator it;
        mt.clear();
        int ans = 0;
        for(i = 0 , j = 0; i < n ; i ++) {
            while(j < n && a[i].ft >= b[j].ft) {
                mt.insert(b[j].sd);
                j ++;
            }    
            if(mt.size()>=1) {
                it = mt.lower_bound(a[i].sd); //大于等于k的第一个元素的位置 
                if(it == mt.end()) it--;
                if(*it > a[i].sd && it != mt.begin()) it--;    
                if(*it <= a[i].sd) {
                    mt.erase(*it);
                    ans ++;   
                }
            }
        }
        printf("%d\n",ans); 
    }
}

还有一个版本 是把两人的矩形放在一起h w id进行排序,其中排序的时候重载的小于号的方法注意学习,然后h肯定是升序的,然后Bob的w插入到multiset,接着如果遇到Alice的矩形,那么h肯定能覆盖multiset中的Bob的h(没有插入h,因为h是升序排的),剩下的就是要根据此时Alice的w去找multiset中刚好比它小一点或者等于它的进行覆盖。

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 100010;
struct rec {
    int h , w , id;
    bool operator <(const rec &b) const {
        if(h != b.h) return h < b.h;
        if(w != b.w) return w < b.w;
        return id < b.id;        
    }    
};
multiset<int> mt;
multiset<int>::iterator it;
rec a[maxn<<1];
int main() {
    int T , n , i , id;       
    scanf("%d",&T);
    while(T --) {
        scanf("%d",&n);
        for(i = 0 ; i < (n<<1) ; i ++) {
            scanf("%d%d",&a[i].h,&a[i].w);
            if(i >= n) a[i].id = 0;
            else a[i].id = 1;    
        } 
        sort(a , a +(n<<1));
        mt.clear();
        int ans = 0;
        for(i = 0 ; i < (n<<1) ; i ++) {
            if(a[i].id == 0) mt.insert(a[i].w);
            else {
                if(!mt.empty()) {
                    if(*mt.begin() <= a[i].w) {
                        it = mt.upper_bound(a[i].w);
                        it--;
                        mt.erase(*it);    
                        ans ++;
                    }    
                }   
            }    
        }
        printf("%d\n",ans);   
    }
}

1006 LianLianKan

题意:题意有歧义,题解是状压、、不会、、貌似模拟可以搞、、、 就是每次消除栈顶元素和向下数6个长度的距离中和其相同的元素,如果最后能消除所有的栈中元素那么输出1,否则输出0

思路:模拟即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
int main() {
    int N , i , j;
    int num;
    int S[1010];
    int vis[1010];
    while(~scanf("%d",&N)) {
        int top = 0;
        for(i = 1 ; i <= N ; i ++) {
            scanf("%d",&num);
            S[top++] = num; 
        }
        if(N%2==1) {
            printf("0\n");
            continue;    
        }
        bool flag;
        memset(vis , 0 , sizeof(vis));
        int cnt = 0;
        int ff = top - 1;
        while(cnt != N) {
            flag = false;
            for(i = top - 1 ; i >= 0 ; i --) {
                if(!vis[i]) {
                    ff = i;
                    for(j = 1 ; j <= 6 ; j ++) {
                        if(S[ff] == S[ff-j] && ff - j >=0) {
                            vis[ff] = 1;
                            vis[ff - j] = 1;
                            flag = true;
                            cnt += 2;
                            break;
                        }    
                    }
                    if(flag) {
                        break;    
                    }  else {
                        goto loop;    
                    }
                }    
            } 
        }
        loop:
        if(!flag) printf("0\n");
        else printf("1\n");
    }    
} 


1011 USACO ORZ

题意:给出一些木棍的长度最多有15根,然后所有的木棒都要用上,求能组成三角形的种类

思路:参考http://www.cnblogs.com/yejinru/archive/2012/09/08/2676899.html 就是把15根木棍放到三条边的位置上,最大复杂度是3^15,每次搜的时候把三条边排序分别放在d[0] ,
d[1] , d[2]中,然后用pair 两条小边和map进行判重,这样搜貌似正好是可以超时,根据对称性直接把a[1]放在第一条边的位置,那么复杂度减小为3^14可以卡过去、、、

#include<iostream>
#include<cstdio>
#include<set>
#include<cstring>
using namespace std;
int a[20] , d[5] , ans , sum , n;
set<pair<int , int> > myset;
void dfs(int i , int suma , int sumb , int sumc) {
    if(i == n+1) {
        if(suma < sumb) {
            d[0] = suma;
            d[1] = sumb;    
        } else {
            d[0] = sumb;
            d[1] = suma;    
        }
        if(sumc < d[0]) d[0] = sumc;
        if(sumc > d[1]) d[1] = sumc;
        d[2] = sum - d[0] - d[1];
        swap(d[2] , d[1]);
        if(d[0] + d[1] <= d[2]) return;
        printf("%d %d %d\n",d[0],d[1],d[2]);
        if(myset.find(make_pair(d[0] , d[1]))!=myset.end()) return;
        ans++;
        myset.insert(make_pair(d[0] , d[1]));
        return;
    }    
    dfs(i + 1 , suma + a[i] , sumb , sumc);
    dfs(i + 1 , suma , sumb + a[i] , sumc);
    dfs(i + 1 , suma , sumb , sumc + a[i]);
}
int main() {
    int T , i;
    scanf("%d",&T);
    while(T --) {
        scanf("%d",&n);
        sum = 0;
        for(i = 1 ; i <= n ; i ++) {
            scanf("%d",&a[i]);
            sum += a[i];    
        }    
        myset.clear();
        ans = 0;
        dfs(2 , a[1] , 0 , 0);
        printf("%d\n",ans);
    }    
}


抱歉!评论已关闭.