WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
2018 Multi-University Training Contest 4
2018 Multi-University Training Contest 4

HDU 6333 Problem B. Harvest of Apples

给定若干个询问,每个询问\sum_{i=0}^m C_n^i

我们把每个询问(m, n)看作一个区间,那么可以使用莫队算法离线处理。

对右区间端点增加(减少相反即可)
\sum_{i=0}^m C_{n+1}^i = \sum_{i=0}^m C_{n}^i + \sum_{i=0}^{m-1} C_{n}^i = 2\cdot C_{n}^{m} + \sum_{i=0}^{m-1} C_{n}^i

对左区间端点增加(减少相反)
\sum_{i=0}^{m+1} C_n^i = \sum_{i=0}^m C_{n}^i + C_n^{m+1}

/**
* Author : WNJXYK
* Date : 20180801
* Problem : 1002
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const int MOD=1e9+7;
const int MAXN=1e5+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n, sn;
struct Query{int l, r, idx;} q[MAXN];

inline bool cmp(const Query &a, const Query &b){
    if ((a.l-1)/sn == (b.l-1)/sn) return a.r<b.r;
    return a.l<b.l;
}

int inv[MAXN], fac[MAXN], ifac[MAXN];
int ans[MAXN];

inline void init(int n){
    inv[1]=fac[0]=ifac[0]=1;
    for (int i=2; i<=n; i++) inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
    for (int i=1; i<=n; i++) fac[i]=1LL*fac[i-1]*i%MOD, ifac[i]=1LL*ifac[i-1]*inv[i]%MOD;
}

inline int getC(int n, int m){return 1LL*fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}
inline void update(int &x){if (x>=MOD) x-=MOD;}

inline void solve(int T){
    scanf("%d", &n); sn=max(1, (int)sqrt(n));
    for (int i=1; i<=n; i++) scanf("%d%d", &q[i].r, &q[i].l), q[i].idx=i;
    sort(q+1, q+n+1, cmp);

    int rate=2;
    for (int i=1, l=1, r=1, tmp; i<=n; i++){
        int L=q[i].l, R=q[i].r;
        while(r<R){
            tmp=getC(r, l);
            rate=rate+MOD-tmp; update(rate);
            rate=rate*2; update(rate);
            rate=rate+tmp; update(rate);
            r++;
        }
        while(l>L){
            rate=rate+MOD-getC(r, l); update(rate);
            l--;
        }
        while(r>R){
            r--;
            tmp=getC(r, l);
            rate=rate+MOD-tmp; update(rate);
            rate=1LL*rate*inv[2]%MOD;
            rate=rate+tmp; update(rate);
        }
        while(l<L){
            l++;
            rate=rate+getC(r, l); update(rate);
        }
        ans[q[i].idx]=rate;
    }

    for (int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    init(1e5+5);
    solve(0);
    return 0;
}

HDU 6335 Problem D. Nothing is Impossible

有若干道有b_i个错误答案,唯一正确答案的选择题。问当有m个学生的情况下,对不同学生的选择进行一番安排之后,对得最多的人最少对几题。

很明显,每道题目对学生b_i+1分组,每个组内其他选项选择相同即可。
所以,贪心对b_i排序,然后贪心模拟即可。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

struct qst {
    int a, b;
}q[10010];

int cmp(qst x, qst y) {
    return x.b < y.b;
}

int main(void)
{
    int t; scanf("%d",&t);
    for(int i = 1; i <= t; ++i) {
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d %d", &q[i].a, &q[i].b);
        sort(q + 1, q + n + 1, cmp);
        LL cur = q[1].b + 1LL;
        int ans = 0, p = 1;
        while(cur <= m && p <= n) {
            ans++;
            p++;
            cur *= q[p].b + 1LL;
            if (cur > m) break;
        }
        printf("%d\n", ans);
    }
    return 0;
}

HDU 6336 Problem E. Matrix from Arrays

给定一个种无限矩阵生成方式,问这个无限矩阵的一个小矩阵内和。

矩阵存在循环节,我们经过讨论循环节之后计算即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long

using namespace std;

const int N = 20;
int L, loop;
int a[N], mat[N][N];
LL cnt[N][N];

int Ceil(int x, int y) {
    return (x+y-1)/y;
}

LL solve(int x, int y) {
    //printf("%lld\n", 1LL*(x+1)*(y+1));
    if(x<0 || y<0) return 0;
    //printf("%d %d\n", x, y);
    memset(cnt, 0, sizeof(cnt));
    LL res = 0;
    for(int i = 0; i < loop; i++)
        for(int j = 0; j < loop; j++) {
            //if(i>x || j>y) continue ;
            int r = Ceil(y-j+1, loop);
            int c = Ceil(x-i+1, loop);
            cnt[i][j] = 1LL*r*c;
            res += cnt[i][j];
        }
    LL ans = 0;
    for(int i = 0; i < loop; i++)
        for(int j = 0; j < loop; j++)
            ans += 1LL*cnt[i][j]*a[mat[i][j]];
    return ans;
}

int main() {
    //freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &L);
        loop = L%2==0 ? L*2:L;
        for(int i = 0; i < L; i++) scanf("%d", &a[i]);
        int cur = 0;
        for(int i = 0; i < 40; i++)
            for(int j = 0; j <= i; j++) {
                if(j<loop && i-j<loop) mat[j][i-j] = cur;
                cur = (cur+1)%L;
            }

        int q;
        scanf("%d", &q);
        int x0, y0, x1, y1;
        while(q--) {
            scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
            printf("%lld\n", solve(x1, y1)-solve(x1, y0-1)-solve(x0-1, y1)+solve(x0-1, y0-1));
        }
    }
}

HDU 6338 Problem G. Depth-First Search

有一个无根树,随意提根DFS,会得到一个DFS序列。给定一个排列,问比这个排列小的DFS序列有多少个。

首先如果固定一个根,那么已这个根的DFS序列数量为等于\prod_{i=1}^n (deg[i]-[i==Root])

问题的其他部分就是确定了之后,确定当前根比这个排列小的序列有多少个,我们只需要DFS一下,统计一下答案即可。

/**
* Author : WNJXYK
* Date : 20180801
* Problem : 1007
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define lowbit(x) ((x) & (-x))
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=1e9+7;
const int MAXN=1e6+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int inv[MAXN], fac[MAXN], ifac[MAXN];
inline void init(int n){
    inv[1]=fac[0]=ifac[0]=1;
    for (int i=2; i<=n; i++) inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
    for (int i=1; i<=n; i++) fac[i]=1LL*fac[i-1]*i%MOD, ifac[i]=1LL*ifac[i-1]*inv[i]%MOD;
}

int dp[MAXN], deg[MAXN], ans;
int B[MAXN], n;
vector<int> edge[MAXN], cnt[MAXN];

int dfsDP(int x, int fa){
    if (fa) edge[x].erase(find(all(edge[x]), fa));
    dp[x]=fac[SZ(edge[x])];
    edge[x].insert(edge[x].begin(), 0); cnt[x].pb(0); cnt[x].pb(0);
    for (int i=1; i<SZ(edge[x]); i++){
        int v=edge[x][i];
        dfsDP(v, x); dp[x]=1LL*dp[x]*dp[v]%MOD;
        cnt[x].pb(0);
    }
}

inline void add(int p, int x, int v) {
    for (; x <= SZ(edge[p]); x += lowbit(x)) cnt[p][x] += v;
}

inline int sum(int p, int x) {
    int ret = 0; for (; x; x -= lowbit(x)) ret += cnt[p][x]; return ret;
}

inline int findNxt(int p, int x) {
    int ps = 0;
    for (int i = 20; i >= 0; --i) if (ps + (1 << i) < SZ(edge[p]) && edge[p][ps + (1 << i)] < x) ps += (1 << i);
    return ps;
}

inline void update(int &x){if (x>=MOD) x-=MOD;}

int idx;
bool dfs(int x, LL V){
    LL now=1; ++idx;
    for (int i=1; i<SZ(edge[x]); i++){
        int v=edge[x][i];
        now=1LL*now*dp[v]%MOD;
        add(x, i, 1);
    }
    for (int i=SZ(edge[x])-2; i>=0; i--){
        int s=findNxt(x, B[idx+1]);
        ans=(ans+1LL*fac[i]*now%MOD*sum(x, s)%MOD*V%MOD)%MOD;
        ++s;
        if (s>=SZ(edge[x]) || edge[x][s]!=B[idx+1]) return true;
        add(x, s, -1); now=1LL*powmod(dp[edge[x][s]], MOD-2)*now%MOD;
        if (dfs(edge[x][s], 1LL*V*fac[i]%MOD*now%MOD)) return true;
    }
    return false;
}

inline void solve(int T){
    scanf("%d", &n);

    // Init
    ans=0;
    for (int i=0; i<=n; i++) edge[i].clear(), cnt[i].clear(), deg[i]=0;

    // Input
    for (int i=1; i<=n; i++) scanf("%d", &B[i]);
    for (int i=1, x, y; i<n; i++) scanf("%d%d", &x, &y), edge[x].pb(y), edge[y].pb(x), ++deg[x], ++deg[y];
    for (int i=1; i<=n; i++) sort(all(edge[i]));

    // Calc Pre
    dp[0]=1;
    for (int i=1; i<=n; i++) dp[0]=1LL*dp[0]*fac[deg[i]-1]%MOD;
    for (int i=1; i<=n; i++) dp[i]=1LL*dp[0]*ifac[deg[i]-1]%MOD*fac[deg[i]]%MOD;
    for (int i=1; i<B[1]; i++) ans=(ans+dp[i])%MOD;

    // Calc Now
    dfsDP(B[1], 0); B[n+1]=0;
    idx=0, dfs(B[1], 1);

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

int main(){
    init(1e6);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 6341 Problem J. Let Sudoku Rotate

给定一个若干格经过随意逆时针旋转的数独,问你将其复原最少顺时针旋转多少次。

暴力搜索即可,因为每行合法的旋转情况很少,所以我们先按行暴力出每行的合法情况,然后在行之间的合法情况中进行暴力搜索。

/**
* Author : WNJXYK
* Date : 20180801
* Problem : 1010
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=16+10;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n, ans;
int mat[MAXN][MAXN];
int now[MAXN][MAXN];
bool vis[16];

inline int read(){
    char x=getchar();
    while(!('0'<=x && x<='F')) x=getchar();
    if ('0'<=x && x<='9') return x-'0';
    return x-'A'+10;
}

vector<PII> line[4];

inline void rotate(int m[MAXN][MAXN], int i, int j){
    i*=4, j*=4; int tmp;
    tmp=m[i+4][j+1], m[i+4][j+1]=m[i+4][j+4], m[i+4][j+4]=m[i+1][j+4], m[i+1][j+4]=m[i+1][j+1], m[i+1][j+1]=tmp;
    tmp=m[i+3][j+1], m[i+3][j+1]=m[i+4][j+3], m[i+4][j+3]=m[i+2][j+4], m[i+2][j+4]=m[i+1][j+2], m[i+1][j+2]=tmp;
    tmp=m[i+2][j+1], m[i+2][j+1]=m[i+4][j+2], m[i+4][j+2]=m[i+3][j+4], m[i+3][j+4]=m[i+1][j+3], m[i+1][j+3]=tmp;
    tmp=m[i+3][j+2], m[i+3][j+2]=m[i+3][j+3], m[i+3][j+3]=m[i+2][j+3], m[i+2][j+3]=m[i+2][j+2], m[i+2][j+2]=tmp;
}

void dfs(int i, int rate){
    if (i==4){
        bool flag=true;
        for (int y=1; y<=16 && flag; y++){
            memset(vis, 0, sizeof(vis));
            for (int x=1; x<=16; x++) vis[now[x][y]]=true;
            for (int j=0; j<16 && flag; j++) flag=flag&&vis[j];
        }
        if (flag) ans=min(ans, rate);
    }else{
        for (int p=0; p<SZ(line[i]); p++){
            int s=line[i][p].fi, c=line[i][p].se;

            for (int x=1; x<=4; x++) for (int y=1; y<=16; y++) now[i*4+x][y]=mat[i*4+x][y];
            for (int j=0; j<4; j++){
                int t=(s>>(j*2))&3;
                for (int p=1; p<=t; p++) rotate(now, i, j);
            }

            dfs(i+1, rate+c);
        }
    }
}

inline void print(int x){
    if (0<=x && x<=9) printf("%c", x+'0'); else printf("%c", x+'A'-10);
}

inline void solve(int T){
    for (int i=1; i<=16; i++) for (int j=1; j<=16; j++) mat[i][j]=read();

    for (int i=0; i<4; i++) line[i].clear();
    for (int i=0; i<4; i++){
        //printf("Line %d\n", i);
        for (int s=0; s<256; s++){
            int cost=0;
            // Gen
            for (int x=1; x<=4; x++) for (int y=1; y<=16; y++) now[i*4+x][y]=mat[i*4+x][y];
            for (int j=0; j<4; j++){
                int t=(s>>(j*2))&3;
                for (int p=1; p<=t; p++) rotate(now, i, j);
                cost+=t;
            }

            // Check
            bool flag=true;
            for (int x=1; x<=4 && flag; x++){
                memset(vis, 0, sizeof(vis));
                for (int y=1; y<=16; y++) vis[now[i*4+x][y]]=true;
                for (int j=0; j<16 && flag; j++) flag=flag&&vis[j];
            }

            // Save
            if (flag) line[i].pb(mp(s, cost));

            // Debug
            /*if (flag){
                for (int x=1; x<=4; x++) {
                    for (int y=1; y<=16; y++) print(now[i*4+x][y]);
                    printf("\n");
                }
                printf("Cost = %d\n", cost);
            }*/
        }
    }

    ans=50;
    dfs(0, 0);
    printf("%d\n", ans);
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

2018 Multi-University Training Contest 4
HDU 6333 Problem B. Harvest of Apples 给定若干个询问,每个询问$$\sum_{i=0}^m C_n^i$$ 我们把每个询问$$(m, n)$$看作一个区间,那么可以使用莫队算法离线处理。 对右区间端点增加…
扫描二维码继续阅读
2018-08-02
<--! http2https -->