发布于 由東風谷早苗（こちやさなえ）

bzoj刷题记录 (1)

1011: [HNOI2008]遥远的行星

利用题目特殊条件暴力+乱搞，详见文章

代码
/*
 DOCUMENT NAME "20181128-bnds1011.cpp"
 CREATION DATE 2018-11-28
 SIGNATURE CODE_20181128_BNDS1011
 COMMENT [HNOI2008]遥远的行星
*/

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;

template<typename IntType>
void read(IntType& val) {
    val = 0;
    int c;
    bool inv = false;
    while (!isdigit(c = getchar()))
        if (c == '-')
            inv = true;
    do {
        val = (val << 1) + (val << 3) + c - '0';
    } while (isdigit(c = getchar()));
    if (inv)
        val = -val;
}

typedef long long ll;
const int MaxN = 1e5 + 10;

int n;
double a;
int m[MaxN];
ll sum[MaxN];


int main(int argc, char* argv[]) {

    read(n);
    scanf("%lf", &a);

    for (int i = 1; i <= n; i++) {
        read(m[i]);
        sum[i] = sum[i - 1] + m[i];
    }

    for (int i = 1; i <= n; i++) {
        int fl = i * a + 1e-7;
        if (i <= 1000) {
            double ans = 0;
            for (int j = 1; j <= fl; j++)
                ans += (double)m[j] * m[i] / (i - j);
            printf("%lf\n", ans);
        } else
            printf("%lf\n", (double)sum[fl] * m[i] / (i - .5*fl));
    }

    return 0;
}

1015: [JSOI2008]星球大战starwar

题目没有要求强制在线，所以可以反着加点，用并查集维护一个点连出的所有边上两个连通块的合并，同时维护连通块大小作为当前点的答案

注意当前点在第一次合并入集合时并查集个数不减一

代码
/*
 DOCUMENT NAME "20181208-bzoj1015.cpp"
 CREATION DATE 2018-12-08
 SIGNATURE CODE_20181208_BZOJ1015
 COMMENT 1015: [JSOI2008]星球大战starwar
*/
 
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
 
template<typename IntType>
void read(IntType& val) {
    val = 0;
    int c;
    bool inv = false;
    while (!isdigit(c = getchar()))
        if (c == '-')
            inv = true;
    do {
        val = (val << 1) + (val << 3) + c - '0';
    } while (isdigit(c = getchar()));
    if (inv)
        val = -val;
}
 
#if (defined LOCAL) || (defined D)
#define DEBUG(...) printf(__VA_ARGS__)
#define PRINTARR(formatstr, arr, beginoff, size)                \
do{printf(#arr ":");                                            \
for (int __i = beginoff; __i <= beginoff + size - 1; __i++)      \
    printf("\t%d", __i);                                        \
printf("\n");                                                   \
for (int __i = beginoff; __i <= beginoff + size - 1; __i++)      \
    printf("\t" formatstr, arr[__i]);                           \
printf("\n"); }while(false)
#define PASS printf("Passing function \"%s\" on line %d\n", __func__, __LINE__)
#define ASSERT(expr) do{\
    if(!(expr)){\
        printf("Debug Assertation Failed on line %d, in function %s:\n  Expression: %s\n",__LINE__,__func__,#expr);\
        abort();\
    }\
}while(false)
#else
#define DEBUG(...)
#define PRINTARR(a, b, c, d)
#define PASS
#define ASSERT(expr)
#endif
 
const int MaxM = 200000 + 10, MaxN = 2 * MaxM;
 
int n, m;
int x[MaxM], y[MaxM];
int k;
int t[MaxN];
bool down[MaxN];
int ans[MaxN];
 
struct node {
    int v;
    node* next;
};
 
node* h[MaxN];
node mem[2 * MaxM], *memtop = mem;
#define ALLOCATE (++memtop)
 
void addedge(int u, int v) {
    node* p = ALLOCATE;
    p->v = v;
    p->next = h[u];
    h[u] = p;
    p = ALLOCATE;
    p->v = u;
    p->next = h[v];
    h[v] = p;
}
 
int p[MaxN];
 
int setfind(int x) {
    if (p[x] < 0)
        return x;
    else
        return p[x] = setfind(p[x]);
}
 
void setunion(int x, int y) {
    x = setfind(x);
    y = setfind(y);
    if (x != y) {
        p[x] += p[y];
        p[y] = x;
    }
}
 
int cnt;
 
 
int main(int argc, char* argv[]) {
 
    read(n); read(m);
    for (int i = 1; i <= m; i++) {
        read(x[i]); read(y[i]);
        x[i]++; y[i]++;
        addedge(x[i], y[i]);
    }
    read(k);
    for (int i = 1; i <= k; i++) {
        read(t[i]);
        t[i]++;
        down[t[i]] = true;
    }
 
    memset(p, -1, sizeof(p));
    for (int i = 1; i <= m; i++) {
        if (!down[x[i]] && !down[y[i]])
            setunion(x[i], y[i]);
    }
 
    PRINTARR("%d", down, 1, n);
    PRINTARR("%d", p, 1, n);
 
    cnt = 0;
    for (int i = 1; i <= n; i++)
        if (!down[i] && p[i] < 0)
            cnt++;
 
    for (int i = k; i >= 1; i--) {
        ans[i] = cnt;
        int u = t[i];
        cnt++;
        down[u] = false;
        for (node* p = h[t[i]]; p; p = p->next) {
            int v = p->v;
            if (!down[v] && setfind(u) != setfind(v)) {
                setunion(u, v);
                cnt--;
            }
        }
    }
    ans[0] = cnt;
 
    for (int i = 0; i <= k; i++)
        printf("%d\n", ans[i]);
 
    return 0;
}

1012: [JSOI2008]最大数maxnumber

直接开一个长为n的线段树，模拟即可

代码
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;
 
#if (defined LOCAL) || (defined D)
#define DEBUG(...) printf(__VA_ARGS__)
#define PRINTARR(formatstr, arr, beginoff, size)                \
do{printf(#arr ":");                                            \
for (int __i = beginoff; __i <= beginoff + size - 1; __i++)     \
    printf("\t%d", __i);                                        \
printf("\n");                                                   \
for (int __i = beginoff; __i <= beginoff + size - 1; __i++)     \
    printf("\t" formatstr, arr[__i]);                           \
printf("\n"); }while(false)
#define PASS printf("Passing function \"%s\" on line %d\n", __func__, __LINE__)
#define ASSERT(expr) do{\
    if(!(expr)){\
        printf("Debug Assertation Failed on line %d, in function %s:\n  Expression: %s\n",__LINE__,__func__,#expr);\
        abort();\
    }\
}while(false)
#else
#define DEBUG(...)
#define PRINTARR(a, b, c, d)
#define PASS
#define ASSERT(expr)
#endif
 
template<typename IntType>
void read(IntType& val) {
    val = 0;
    int c;
    bool inv = false;
    while (!isdigit(c = getchar()))
        if (c == '-')
            inv = true;
    do {
        val = (val << 1) + (val << 3) + c - '0';
    } while (isdigit(c = getchar()));
    if (inv)
        val = -val;
}
 
char getnextchar(){
    int c;
    while(iscntrl(c=getchar())||c==' '||c=='\t');
    return c;
}
 
typedef long long ll;
const int MaxN=200000+10;
 
int m;
ll p;
 
struct node{
    int left,right;
    ll max;
    node* lson,*rson;
};
 
node* root;
node mem[2*MaxN],*memtop=mem;
#define ALLOCATE (++memtop)
 
void build(int left=1,int right=m,node*& p=root){
    p=ALLOCATE;
    p->left=left;
    p->right=right;
    if(left==right){
        //p->max=0;
    }else{
        int mid=(left+right)/2;
        build(left,mid,p->lson);
        build(mid+1,right,p->rson);
        //p->max=max(p->lson->max,p->rson->max);
    }
}
 
void setpnt(int pos,int val,node* p=root){
    if(p->left==p->right){
        ASSERT(p->left==pos);
        p->max=val;
        return;
    }
    if(p->lson->right>=pos)
        setpnt(pos,val,p->lson);
    else
        setpnt(pos,val,p->rson);
    p->max=max(p->lson->max,p->rson->max);
}
 
int querymax(int left,int right,node* p=root){
    if(p->left==left&&p->right==right)
        return p->max;
    if(p->lson->right>=right)
        return querymax(left,right,p->lson);
    else if(p->rson->left<=left)
        return querymax(left,right,p->rson);
    else
        return max(querymax(left,p->lson->right,p->lson),
                   querymax(p->rson->left,right,p->rson));
}
 
 
int main(int argc, char* argv[]) {
     
    read(m);read(p);
    build();
 
    int len=0,t=0;
    for(int i=1;i<=m;i++){
        int c,x;
        c=getnextchar();
        read(x);
        if(c=='A')
            setpnt(++len,(x+t)%p);
        else if(c=='Q')
            printf("%d\n",t=querymax(len-x+1,len));
    }
     
    return 0;
}

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注