2017 ICPC 沈阳

淩亂°似流年 2023-10-11 13:27 53阅读 0赞

F.1:27:58(-3) solved by hl

打表发现所有满足条件的t可以通过f(n) = 4 \* f(n - 1) - f(n - 2)递推出来

用\_\_int128或者JAVA大数实现

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

G.3:49:14(-1) solved by hl

答案的长度为N,假设答案有N层，每一层代表一位

设置一个栈表示当前所有可行的结点，显然可行结点的条件是结点表示的字符在这一层中最大。(贪心)

每次在上一层节点中找出可行的下一层结点递推

由于他的边是类似于随机构造的，出题人卡不掉我们

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    using namespace std;
    const int maxn = 2e6 + 10;
    int N;
    int to[maxn];
    struct Edge{
        int to,next;
    }edge[maxn * 2];
    int head[maxn],tot;
    void init(){
        for(int i = 0 ; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    int Stack[2][maxn];
    bool vis[maxn];
    char str[maxn],ans[maxn];
    int main(){
        int T; Sca(T); int CASE = 1;
        while(T--){
            Sca(N); scanf("%s",str);
            char Max = '0';
            for(int i = 0 ; str[i]; i ++) Max = max(Max,str[i]);
            for(LL i = 0 ; i < N; i ++){
                to[i] = (i * i + 1) % N;
            }
            int top[2];
            top[0] = top[1] = 0;
            ans[1] = Max;
            for(int i = 0 ; i < N ; i ++){
                if(str[i] == Max) Stack[1][++top[1]] = i;
            }
            for(int i = 2; i <= N; i ++){
                char Max = '0';
                for(int j = 1; j <= top[i + 1 & 1]; j ++){
                    int v = Stack[i + 1 & 1][j];
                    Max = max(Max,str[to[v]]);
                }
                ans[i] = Max;
                for(int j = 1; j <= top[i + 1 & 1]; j ++){
                    int v = Stack[i + 1 & 1][j];
                    if(str[to[v]] < Max) continue;
                    if(vis[to[v]]) continue;
                    vis[to[v]] = 1;
                    Stack[i & 1][++top[i & 1]] = to[v];
                }
                for(int j = 1; j <= top[i & 1]; j ++) vis[Stack[i & 1][j]] = 0;
                top[i + 1 & 1] = 0;
            }
            printf("Case #%d: ",CASE++);
            for(int i = 1 ; i <= N; i ++) printf("%c",ans[i]);
            puts("");
        }
        return 0;
    }
    /*
    4
    3
    149
    5
    12345
    1
    7
    3214567
    9
    261025520
    */

I.0:30:55(-1) solved by hl

4个2 ^ 62相加会爆ULL

特判一下或者直接上大数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

K.0:26:27 solved by zcz

推公式

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include<cstring>
    #include<cstdio>
    
    using namespace std;
    
    int a[505];
    
    int main()
    {
        int T;
        cin>>T;
        int n;
        while(T--)
        {
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            printf("%d\n",a[n]-a[1]-n+1-min(a[2]-a[1]-1,a[n]-a[n-1]-1));
        }
        return 0;
    }

L.1:10:36 solved by hl

一条边成立（计入贡献）的条件是这条边两端点形成的子树size >= K

dfs求一个子树和就可以了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    using namespace std;
    const int maxn = 2e5 + 10;
    struct Edge{
        int to,next;
    }edge[maxn * 2];
    int head[maxn],tot;
    int N,K;
    void init(){
        for(int i = 0 ; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    int sz[maxn];
    void dfs(int t,int la){
        sz[t] = 1;
        for(int i = head[t]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la) continue;
            dfs(v,t);
            sz[t] += sz[v];
        }
    }
    int ans = 0;
    void dfs2(int u,int la){
        for(int i = head[u]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la) continue;
            if(sz[v] >= K && N - sz[v] >= K) ans++;
            dfs2(v,u);
        }
    }
    int main(){
        int T; Sca(T);
        while(T--){
            Sca2(N,K); init();
            for(int i = 1; i <= N - 1; i ++){
                int u,v; Sca2(u,v);
                add(u,v); add(v,u);
            }
            dfs(1,-1); ans = 0;
            dfs2(1,-1);
            Pri(ans);
        }
        return 0;
    }

M.4:21:33 solved by zcz and hl

设置每个点的权值为他上下左右可以移动的方向 + 它本身

即一个点初始为5,四周边每有一个障碍物 - 1，它本身就是障碍物为0

最终答案就是右下角三角形的 (N \* (N - 1) / 2)个点的权值和 / 所有点的权值和

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    using namespace std;
    const int maxn = 2e6 + 10;
    LL N,K;
    map<PII,int>Q;
    map<PII,bool> vis;
    int id(int x,int y){
        int sum = 5;
        if(x == N || x == 1) sum--;
        if(y == N || y == 1) sum--;
        sum -= Q[mp(x,y)];
        return sum;
    }
    int main(){
        int T; Sca(T); int CASE = 1;
        while(T--){
            Scl(N); Scl(K); Q.clear(); vis.clear();
            LL sum =  N * (N + 1) / 2;
            LL up = 0;
            up = (N - 2) * 4 * 2 + 9;
            up += (sum - N - (N - 1)) * 5;
            LL down = (N - 2) * 4 * 4 + 4 * 3 + (N - 2) * (N - 2) * 5;
            LL dd = 0,du = 0;
            for(int i = 1; i <= K ; i ++){
                int x,y;
                Sca2(x,y); x++; y++;
                if(x != 1 && !vis[mp(x - 1,y)]){
                    if(x - 1 + y >= N + 1) du++;
                    dd++;
                    Q[mp(x - 1,y)]++;
                }
                if(x != N && !vis[mp(x + 1,y)]){
                    if(x + 1 + y >= N + 1) du++;
                    dd++;
                    Q[mp(x + 1,y)]++;
                }
                 if(y != 1 && !vis[mp(x,y - 1)]){
                    if(x - 1 + y >= N + 1) du++;
                    dd++;
                    Q[mp(x,y - 1)]++;
                }
                if(y != N && !vis[mp(x,y + 1)]){
                    if(x + 1 + y >= N + 1) du++;
                    dd++;
                    Q[mp(x,y + 1)]++;
                }
                vis[mp(x,y)] = 1;
                if(x + y >= N + 1) du += id(x,y);
                dd += id(x,y);
            }
            up -= du;
            down -= dd;
            LL g = __gcd(up,down);
            up /= g; down /= g;
            printf("Case #%d: %lld/%lld\n",CASE++,up,down);
        }
        return 0;
    }
    /*
    4
    3
    149
    5
    12345
    1
    7
    3214567
    9
    261025520
    */

转载于:https://www.cnblogs.com/Hugh-Locke/p/11347520.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif