HZNU Training 1 for Zhejiang Provincial Collegiate Programming Contest

赛后总结：

　　TJ：今天我先到实验室，开始看题，一眼就看了一道防AK的题目，还居然觉得自己能做wwww。然后金姐和彭彭来了以后，我和他们讲了点题目。然后金姐开始搞dfs，我和彭彭看榜研究F题。想了很久脑子都炸了，做不下去了。然后在等金姐做完以后，彭彭说了D题题意，然后金姐开始写另外一道搜索题。做完两道搜索以后，金姐让我写那道线段树的题目。我搞了很久。。。然后超时了，因为要用素数筛，然后加了素数筛也做不出呜呜。金姐和彭彭把Ant的题目公式给搞出来了。开始敲。后来是因为取模的问题，就一直没搞成功。比赛吃完饭回来搞了一下，就。。ac了。

　　呜呜呜，我要更努力，不给队友拖后腿。

　　JZH：今天又迟到了，上完体育课要从a区到b区，好痛苦。刚开始先看了B题，想到了LCIS，结果n太大不能dp，然后就没思路了。。。。然后彭彭让我去做了C题，但是不够仔细，WA了三发才A。做完之后，看了下F题，没思路，听彭彭讲了D题题意，就去做了D题，结果忘记用优先队列和把队列清空，又WA了两发才A （明明打的时候提醒过自己要用优先队列）。然后就去推H题的公式了，结果推出来又因为取模的原因一直过不了。

　　真是曲折的一天。继续努力！

PJW：到实验室，题目都还没打开，谭总就来跟我讲了一道防AK题。但也忘了为啥没有死磕。跟了榜，我看了D，让金姐看了C，然后。。。我理解错了题意，觉得D题我来解决可能有点难度，就让金姐敲了。。F题是和谭总一起看的，觉得好绕啊，就是没想到DP（虽然贪心也能做）后来。。我开了一道线段树的题目，谭总开了一道Ant，然而是谭总打得线段树，我和金姐看的Ant（我一边继续磕F题，一边帮金姐验算）第一遍开头就错了。。后来因为取模问题，我改代码的时候有想到要分类考虑。。然而可能还是觉得自己“强”的不用分类，就结束了还是WA。去吃饭的路上，都在讨论为什么WA，然后就得出了分类讨论。

我一直都是个打酱油的～～

题解：

A.Pocket Cube HDU - 4801

　给你一块2*2*2的魔方，问你在n步内能拼成的最多的面有多少。

　一共有6*2种旋转方法，但是因为一边旋转，相当于另一边也在旋转，所以只需要列举6种情况。

借用一下https://www.cnblogs.com/linkzijun/p/7050040.html的图。

然后dfs暴力一下就好了。注意数字不要填错wwww。填错了，检查的眼睛痛。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
const int maxn = 2e5 + 50;
#define MAX_DISTANCE 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define ll long long
#define SIGN(A) ((A > 0) ? 1 : -1) 
#define NO_DISTANCE 1000000
const int INF = 0x3f3f3f3f;
#define LL long long int 
#define mod 1000000007
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
int maxx;
int N;
int trans[7][24] = {
    {0,1,8,14,4,3,7,13,17,9,10,2,6,12,16,15,5,11,18,19,20,21,22,23},
    {0,1,11,5,4,16,12,6,2,9,10,17,13,7,3,15,14,8,18,19,20,21,22,23},
    {6,1,12,3,5,11,16,7,8,9,4,10,18,13,14,15,20,17,22,19,0,21,2,23},
    {20,1,22,3,10,4,0,7,8,9,11,5,2,13,14,15,6,17,12,19,16,21,18,23},
    {1,3,0,2,23,22,4,5,6,7,10,11,12,13,14,15,16,17,18,19,20,21,9,8},
    {2,0,3,1,6,7,8,9,23,22,10,11,12,13,14,15,16,17,18,19,20,21,5,4},
};

void dfs(int a[],int step)
{
    int num = 0;
    if (a[0] == a[1] && a[0] == a[2] && a[0] == a[3])
        num++;
    if (a[4] == a[5] && a[4] == a[10] && a[4] == a[11])
        num++;
    if (a[6] == a[7] && a[6] == a[12] && a[6] == a[13])
        num++;
    if (a[8] == a[9] && a[8] == a[14] && a[8] == a[15])
        num++;
    if (a[16] == a[17] && a[16] == a[18] && a[16] == a[19])
        num++;
    if (a[20] == a[21] && a[20] == a[22] && a[20] == a[23])
        num++;
    maxx = max(maxx, num);
    if (step == N || maxx == 6)
        return;
    int m[24];
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 24; j++)
        {
            m[j] = a[trans[i][j]];
        }
        dfs(m, step + 1);
    }
}
int main()
{
    while (scanf("%d", &N) != EOF)
    {
        maxx = 0;
        int a[50];
        for (int i = 0; i < 24; i++)
            cin >> a[i];
        dfs(a, 0);
        cout << maxx << endl;
    }
    system("pause");
    return 0;
}

View Code

C.Seeding ZOJ - 2100

农民开始播种。在n*m的田地上有几块石头，一开始机器从左上角点开始出发，问是否开机器，经过田地上的每个点只用一次，大石头不能到达。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
const int MAXN = 2e5+50;
#define MAX_DISTANCE 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define ll long long
#define SIGN(A) ((A > 0) ? 1 : -1) 
#define NO_DISTANCE 1000000
int n, m, sum;
char a[100][100];
int vis[100][100];
int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };
bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || a[x][y] == 'S')
        return false;
    return true;
}
bool dfs(int x, int y, int k)
{
    if (k <= 1) return true;
    vis[x][y] = 1;
    for (int i = 0; i < 4; ++i)
    {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (check(xx, yy))
        {
            if (dfs(xx, yy, k - 1)) return true;
            vis[xx][yy] = 0;
        }
    }
    return false;
}
int main()
{
    while (scanf("%d %d", &n, &m), n || m)
    {
        mm(vis, 0);
        for (int i = 0; i < n; ++i)
            scanf("%s", a[i]);
        sum = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (a[i][j] == '.')
                    sum++;
            }
        }
        if (dfs(0, 0, sum)) printf("YES\n");
        else printf("NO\n");
    }
    
    //system("pause");
    return 0;
}

View Code

D:D - Rescue ZOJ - 1649

天使的朋友营救天使，经过一个点用花费1时间，打败guard需要花费1（可打败所有guard），问最后营救天使最少需要花费多少时间。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
const int MAXN = 2e5 + 50;
#define MAX_DISTANCE 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define ll long long
#define SIGN(A) ((A > 0) ? 1 : -1) 
#define NO_DISTANCE 1000000
int n, m, sum;
char a[300][300];
int vis[300][300];
int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };
bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || a[x][y] == '#')
        return false;
    return true;
}
struct node {
    int x, y, t;
    bool friend operator <(node a, node b) {
        return a.t > b.t;
    }
};
priority_queue<node>q;
int bfs()
{
    while (!q.empty())
    {
        node now = q.top();
        q.pop();
        //cout << now.x << " " << now.y <<" "<<now.t<< endl;
        if (a[now.x][now.y] == 'a') return now.t;

        for (int i = 0; i < 4; ++i)
        {
            int xx = now.x + dir[i][0];
            int yy = now.y + dir[i][1];
            if (check(xx, yy))
            {
                vis[xx][yy] = 1;
                if (a[xx][yy] == 'x')
                    q.push(node{ xx,yy,now.t + 2 });
                else
                    q.push(node{ xx,yy,now.t + 1 });
            }
        }
    }
    return -1;
}
int main()
{
    while (~scanf("%d %d", &n, &m))
    {
        mm(vis, 0);
        while (!q.empty())
            q.pop();
        for (int i = 0; i < n; ++i)
            scanf("%s", a[i]);
        sum = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (a[i][j] == 'r')
                {
                    q.push(node{ i,j,0 });
                    vis[i][j] = 1;
                }
            }
        }
        int time = bfs();
        if (time == -1)
            printf("Poor ANGEL has to stay in the prison all his life.\n");
        else
            printf("%d\n", time);
    }

    //system("pause");
    return 0;
}

View Code

F - Cake ZOJ - 3905

A和B去买蛋糕，一共买了n块蛋糕（n为偶数）。每块蛋糕对A和B的价值是不一样的。每次A从n块蛋糕里选择两块，然后B选择一块对于他来说，价值最大的值。求n/2轮以后，A获得的最大的价值为多少。

是一道dp题目。dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+cake[i].a)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
const int maxn = 2e5 + 50;
#define MAX_DISTANCE 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define ll long long
#define SIGN(A) ((A > 0) ? 1 : -1) 
#define NO_DISTANCE 1000000
const int INF = 0x3f3f3f3f;
#define LL long long int 
#define mod 1000000007
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
const int N = 10;
struct Cake
{
    int a;
    int b;
}cake[1000];
int dp[1000][1000];
bool cmp(Cake aa, Cake bb)
{
    return aa.b > bb.b;
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(dp, 0, sizeof(dp));
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> cake[i].a >> cake[i].b;
        sort(cake + 1, cake + 1 + n, cmp);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= i / 2; j++)
            {
                if (j > 0)
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + cake[i].a);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        cout << dp[n][n / 2] << endl;
    }
    //system("pause");
    return 0;
}

View Code

G - Prime Query ZOJ - 3911

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mid(a,b) ((a+b)>>1)
#define LL int
#define maxn 110000
#define IN freopen("in.txt","r",stdin);
using namespace std;

char is_prime[maxn*100];
void sieve()
{
    int m=(int)sqrt((maxn*100)+0.5);
    fill(is_prime,is_prime+(maxn*100),1);
    is_prime[0]=is_prime[1]=0;
    for(int i=2;i<=m;i++) if(is_prime[i])
        for(int j=i*i;j<(maxn*100);j+=i) is_prime[j]=0;
}

int n,q;
LL num[maxn];
struct Tree
{
    int left,right;
    LL sum;
    LL val,lazy;
}tree[maxn<<2];


/*递归建树*/
void build(int i,int left,int right)
{
    tree[i].left=left;
    tree[i].right=right;
    tree[i].lazy=0;

    if(left==right){
        tree[i].val=num[left];
        tree[i].sum=(is_prime[num[left]]? 1:0);
        return ;
    }

    int mid=mid(left,right);

    build(i<<1,left,mid);
    build(i<<1|1,mid+1,right);

    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
}

/*区间修改，标记下传：每当访问到当前结点的子节点时，下传标记*/
void pushdown(int i)
{
    if(tree[i].lazy){
        int tmp = (is_prime[tree[i].lazy]? 1:0);
        tree[i<<1].val=tree[i].lazy;
        tree[i<<1|1].val=tree[i].lazy;
        tree[i<<1].lazy=tree[i].lazy;
        tree[i<<1|1].lazy=tree[i].lazy;
        tree[i<<1].sum=(tree[i<<1].right-tree[i<<1].left+1)*tmp;
        tree[i<<1|1].sum=(tree[i<<1|1].right-tree[i<<1|1].left+1)*tmp;
        tree[i].lazy=0; /*下传后清零*/
    }
}

/*区间修改，d为改变量*/
void update(int i,int left,int right,LL d)
{
    if(tree[i].left==left&&tree[i].right==right)
    {
        int tmp = (is_prime[d]? 1:0);
        tree[i].sum=(right-left+1)*tmp;
        tree[i].val=d;
        tree[i].lazy=d;
        return ;
    }

    pushdown(i);

    int mid=mid(tree[i].left,tree[i].right);

    if(right<=mid) update(i<<1,left,right,d);
    else if(left>mid) update(i<<1|1,left,right,d);
    else
    {
        update(i<<1,left,mid,d);
        update(i<<1|1,mid+1,right,d);
    }

    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
}

/*单点修改，d为改变量*/
void update(int i,int x,LL d)
{
    if(tree[i].left==tree[i].right){
        tree[i].val+=d;
        tree[i].sum=(is_prime[tree[i].val]? 1:0);
        return;
    }

    pushdown(i);
    int mid=mid(tree[i].left,tree[i].right);

    if(x<=mid) update(i<<1,x,d);
    else update(i<<1|1,x,d);

    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
}

/*区间结果查询*/
LL query(int i,int left,int right)
{
    if(tree[i].left==left&&tree[i].right==right)
        return tree[i].sum;

    pushdown(i);

    int mid=mid(tree[i].left,tree[i].right);

    if(right<=mid) return query(i<<1,left,right);
    else if(left>mid) return query(i<<1|1,left,right);
    else return query(i<<1,left,mid)+query(i<<1|1,mid+1,right);
}


int main(int argc, char const *argv[])
{
    //IN;

    sieve();
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&q);
        for(int i=1;i<=n;i++) scanf("%d",&num[i]);
        build(1,1,n);

        while(q--)
        {
            char c;
            while(c=getchar()){
                if(c=='A'||c=='R'||c=='Q') break;
            }
            if(c=='A'){
                int v,l;
                scanf("%d %d",&v,&l);
                update(1,l,v);
            }
            if(c=='R'){
                int a,l,r;
                scanf("%d %d %d",&a,&l,&r);
                update(1,l,r,a);
            }
            if(c=='Q'){
                int l,r;
                scanf("%d %d",&l,&r);
                printf("%d\n", query(1,l,r));
            }
        }
    }

    return 0;
}

View Code

H：Ant ZOJ - 3903

小蚂蚁从立方体角上的一点爬到立方体对面的点，给你一条最长的一边n长度，另外两条边1<=a，b<=n，问所有最短长度L^2的合（答案对1e9+7取模）。

公式：

L^2=(n*n)*(n*(n+1))/2+(n*n)*(n+1)*(n+1)/2+n*(n+1)*(2*n+1)*(n+2)/6;

(具体看代码)

因为n的范围在1~10^14，所以计算取模的时候一定要小心。还有在/6的时候需要进行特判。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
const int maxn = 2e5 + 50;
#define MAX_DISTANCE 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define ll long long
#define SIGN(A) ((A > 0) ? 1 : -1)
#define NO_DISTANCE 1000000
const int INF = 0x3f3f3f3f;
#define LL long long int
#define mod 1000000007


int main()
{
    int t;
    ll n;
    cin >> t;
    while (t--)
    {
        scanf("%lld", &n);
        n %= mod;
        ll ans = (n*(n + 1) / 2) % mod*((n * n) % mod);
        ans = (ans + (((n*(n + 1) / 2) % mod)*((n*(n + 1) / 2) % mod)) % mod) % mod;
        if (n % 3 == 0||(n+1)%3==0) {
            ans = (ans + (((n*(n + 1) / 6) % mod)*(((2 * n + 1)*(n + 2)) % mod))) % mod;
        }
        else {
            ans = (ans + (((n*(n + 1) / 2) % mod)*(((2 * n + 1)*(n + 2)/3) % mod))) % mod;
        }
        //ans = (ans + (((n*(n + 1) / 2) % mod)*(((2 * n + 1)*(n + 2)) % mod) / 3)) % mod;
        //
       // ll ans = ((((n * n) % mod )*n % mod) *(n + 1)) % mod / 2;
        //ans = (ans + ((((n * n % mod) *(n + 1) % mod)*(n + 1) % mod)%mod )/ 4) % mod;
        //ans = (ans + (((n * (n + 1) % mod)*((2 * n + 1) % mod ) % mod)%mod*(n + 2) % mod) / 6) % mod;
        cout << ans << endl;
    }
    //system("pause");
    return 0;
}

View Code

K - Asteroids POJ - 3041

一个n*n的二维坐标上，有k个星星，给你星星的位置（x，y都为整数），可以一整排一整列消灭星星，问最少需要几步。

思路：https://blog.csdn.net/u013480600/article/details/38615197

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
const int maxn = 1000;
#define MAX_DISTANCE 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define ll long long
#define SIGN(A) ((A > 0) ? 1 : -1) 
#define NO_DISTANCE 1000000
const int INF = 0x3f3f3f3f;
#define LL long long int 
#define mod 1000000007
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }

struct Max_Match
{
    int n;
    bool g[maxn][maxn];
    bool vis[maxn*2];
    int left[maxn*2];
    void init(int n)
    {
        this->n = n;
        memset(g, 0, sizeof(g));
        memset(left, -1, sizeof(left));
    }
    
    bool match(int u)
    {
        for (int v = 1; v <= n; v++)
        {
            if (g[u][v] && !vis[v])
            {
                vis[v] = true;
                if (left[v] == -1 || match(left[v]))
                {
                    left[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            memset(vis, 0, sizeof(vis));
            if (match(i))
                ans++;
        }
        return ans;
    }
    
}MM;

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    MM.init(n);
    while (k--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        MM.g[u][v] = true;
    }
    printf("%d\n", MM.solve());
    return 0;
}

View Code