2018 Multi-University Training Contest 4 E,J,K

Problem E. Matrix from Arrays

---

打表得出规律，每个2*len的区域都相等。
预处理二维前缀和。
求给出的坐标左上角区域包含多少个2*len为边长的区域，多出的再处理。（calc）

---

已经找出规律，差点容斥，没有想下去…

---

一点容斥，黑色+，黄色-

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
#define ll long long
const int N = 1e3+5;
int a[N];
ll m[N][N];
int t, len, q, x1, y1, x2, y2;

ll calc(int x, int y)
{
    if(x<0 || y<0) return 0;
    return 1ll*m[len-1][len-1]*(x/len)*(y/len) + 
    1ll*m[x%len][len-1]*(y/len) + 
    1ll*m[len-1][y%len]*(x/len) + 
    1ll*m[x%len][y%len];
}

void init()
{
    int cursor = 0;
    for (int i = 0; i<=4*len; ++i) {///打全2*len,2*len的区域
        for (int j = 0; j <= i; ++j) {
            m[j][i - j] = a[cursor];
            cursor = (cursor + 1) % len;
        }
    }
    len *= 2;///以len为边长的区域与其他区域中的数相等
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            if(i) m[i][j] += m[i-1][j];
            if(j) m[i][j] += m[i][j-1];
            if(i && j) m[i][j] -= m[i-1][j-1];///二维前缀和
        }
    }
}
int main()
{
    scanf("%d", &t);
    while(t --){
        scanf("%d", &len);
        for(int i=0; i<len; i++){
            scanf("%d", &a[i]);
        }
        init();
        scanf("%d", &q);
        for(int i=0; i<q; i++){
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            printf("%lld\n", calc(x2, y2) - calc(x2, y1-1) - calc(x1-1, y2) + calc(x1-1, y1-1));///-1
            ///见上图，要求的是只有黑色喷枪覆盖的区域
        }
    }
    return 0;
}

Problem J. Let Sudoku Rotate
dls dalao代码

---

给出16*16的数独，分成多个4*4的区域，求最少顺时针旋转这些区域得到合法的数独。

---

第一行开始，从左到右dfs+可行性剪枝

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 20;
char s[N][N], v[N][N];
int t, ans;

void rot(int a, int b)///顺时针旋转
{
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            v[j][3-i] = s[a+i][b+j];///v[j][len-i-1]
        }
    }
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            s[a+i][b+j] = v[i][j];
        }
    }
}
int cnt;
int vis[N];
bool check(int a, int b)///以(a,b)为左上角的正方形区域是否合法
{
    for(int i=a; i<a+4; i++){
        ++ cnt;
        for(int j=0; j<b+4; j++){
            if(vis[s[i][j]] == cnt)
                return false;
            vis[s[i][j]] = cnt;
        }
    }
    for(int i=b; i<b+4; i++){
        ++ cnt;
        for(int j=0; j<a+4; j++){
            if(vis[s[j][i]] == cnt)
                return false;
            vis[s[j][i]] = cnt;
        }
    }
    return true;
}
void dfs(int i, int j, int k)
{
    if(i == 4){///遍历完一次
        ans = min(ans, k);
        return;
    }
    if(k >= ans)///可行性剪枝
        return;
    if(j == 4)///下一行
        return dfs(i+1, 0, k);
    for(int t=0; t<4; t++){///转四次
        if(check(i*4, j*4))
            dfs(i, j+1, k+t);///k+t
        rot(i*4, j*4);
    }
}

int main()
{
    scanf("%d", &t);
    while(t --){
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<16; i++){
            scanf("%s", s[i]);///& X
        }
        for(int i=0; i<16; i++){///
            for(int j=0; j<16; j++){
                if(s[i][j]<='9')
                    s[i][j] -= '0';
                else
                    s[i][j] = s[i][j]-'A'+10;
            }
        }
//试着输出，都是乱码
//        printf("\n");
//        for(int i=0; i<16; i++){
//            for(int j=0; j<16; j++){
//                printf("%c", s[i][j]);
//            }printf("\n");
//        }
        ans = 1000;
        dfs(0, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

Problem K. Expression in Memories

---

给出一串符号，求是否能得到合法的符号串。
0? => +/*
+? => 1
*? =>1

---

代码臭长，还得疯狂找样例

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+5;
char str[N];
int t, zero, flag, num, ans;

void init()
{
    zero = flag = num = 0;///前面有0，有符号，有合法数字
}

int main()
{
    scanf("%d", &t);
    while(t --){
        init();
        ans = 0;
        scanf("%s", str);
        int len = strlen(str);
        if(str[0]=='?')///首尾有?
            str[0] = '1';
        if(str[len-1]=='?')
            str[len-1] = '1';

        for(int i=1; i<len-1; i++)///符号旁的?都为赋为1
            if(str[i] == '?')
                if(str[i-1]=='+'||str[i-1]=='*'||str[i+1]=='+'||str[i+1]=='*')
                    str[i] = '1';

        if(str[0]=='+'||str[0]=='*')///第一位
            ans = -1;
        if(str[len-1]=='+'||str[len-1]=='*')///最后一位
            ans = -1;

        for(int i=0; i<len; i++){
            if(zero==1 && str[i]=='?'){///0?
                str[i] = '+';
                init(), flag = 1;
                continue;
            }
            if(flag==1 && str[i]=='?'){///0?? -> 0+?
                str[i] = '1';
                init(), num = 1;
                continue;
            }
            if(num==1 && str[i]=='?')///1?
                str[i] = '1';
            if(zero==1 && ('0'<=str[i] && str[i]<='9'))///01
                ans = -1;
            if(flag==1 && (str[i]=='+'||str[i]=='*'))///+*
                ans = -1;
            if(str[i]=='+'||str[i]=='*')///符号
                init(), flag = 1;
            else if('0'<str[i] && str[i]<='9')///数字
                init(), num = 1;
            else if(str[i]=='0'){///0
                if(num == 1) continue;
                else init(), zero = 1;
            }
            if(ans == -1) break;
        }
        if(ans == -1){
            printf("IMPOSSIBLE\n");
        }
        else{
            for(int i=0; i<len; i++){
                if(str[i]=='?')
                    printf("1");
                else
                    printf("%c", str[i]);
            }
            printf("\n");
        }
    }
    return 0;
}
///?1?3+??+3
///100000
///1+01
///1+*2
///+1+1
///+1*+1
///01+001
///100000*
///0??0?+?+?0?+0??