【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（4）

谁借莪１个温暖的怀抱￠ 2022-08-29 09:59 77阅读 0赞

### 文章目录 ###

*  1001 Calculus 数学思维
 *  1002 Kanade Loves Maze Designing 思维
 *  1007 Increasing Subsequence DP
 *  1008 Lawn of the Dead 线段树
 *  1009 License Plate Recognition 思维

题目集地址[2021“MINIEYE杯”中国大学生算法设计超级联赛（4）][2021_MINIEYE_4]  
题目集原地址[2021“MINIEYE杯”中国大学生算法设计超级联赛（4）][2021_MINIEYE_4 1]  
这次题目集我们只做出两个简单题1001和1009

# 1001 Calculus 数学思维 #

[1001 Calculus][]  
题意：就是给出一个多项式，让你求多项式x从1到正无穷的累和是否是收敛的，组成多项式的单项式只有固定的几种格式。  
思路：经过分析发现，给出的单项式的格式中，所有单项式都是发散的。除非某一项为零。于是解题的重点在于，分析某一项是否为零。我是将所有单项式分离出来，逐个判断的。  
AC代码：

#include <bits/stdc++.h>
    using namespace std;
    string strs[101];
    void solve(string str)
    { 
        int p = 0;
        int cnt = 1;
        while((p = str.find("+",p+1)) != -1)
        { 
            str.replace(p,1," ");
            cnt++;
        }
        stringstream ss(str);
        for(int i = 1;i <= cnt;i++)
        { 
            ss >> strs[i];
        }
    
        for(int i = 1;i <= cnt;i++)
        { 
            if(strs[i][0]!='0')
            { 
                cout << "NO" << endl;
                return;
            }
        }
        cout << "YES" << endl;
        return;
    }
    int main()
    { 
        cin.sync_with_stdio(0);
        cin.tie(0);
        int t;
        cin >> t;
        string str;
        while(t--)
        { 
            cin >> str;
            solve(str);
        }
        return 0;
    }

# 1002 Kanade Loves Maze Designing 思维 #

题目地址【[1002 Kanade Loves Maze Designing][]】  
题意：一棵n个结点的树，每一个结点都有一个值，a(i,j)表示结点i到结点j路径上的不同的值的个数，矩阵a长宽都是n，求  
![在这里插入图片描述][07cea4d299f246f98927c9b680deb506.png]

思路：考虑用 ±1 法统计每种颜色即可。即，记cnt\[i\]为颜色i的出现次数，ans为从某点处开始 DFS，到点j得到的答案，进入该点时，给cnt\[x\]加一，如果这种颜色第一次出现，则给ans加一，记录答案，退出该点时给cnt\[x\]减1，如果给cnt\[x\]减一后这种颜色不会出现，则ans减一 。  
AC代码：

/* ** Author:白马非马队 ** Time:7-29 ** function:杭电第4次1002题 */
    #include <bits/stdc++.h>
    #define ll long long
    #define lll __int128
    using namespace std;
    
    const ll X = 19560929;
    const ll mod1 = 1e9+7;
    const ll mod2 = 1e9+9;
    const int maxn = 2001;
    
    int _1[maxn],_2[maxn];
    int c[maxn];
    int cnt[maxn],p[maxn];
    vector<int> v[maxn];
    int ans;
    void init(int n)
    { 
        _1[0] = 1;_2[0]=1;
        for(int i = 1;i<=n;i++)
        { 
            _1[i] = 1LL*_1[i-1]*X%mod1;
            _2[i] = 1LL*_2[i-1]*X%mod2;
        }
    }
    void add(int m)
    { 
        if(!cnt[m])
        { 
            ans++;
        }
        ++cnt[m];
    }
    void del(int m)
    { 
        --cnt[m];
        if(!cnt[m])
        { 
            ans--;
        }
    }
    void DFS(int m,int n)
    { 
        add(c[m]);
        p[m] = ans;
        for(auto f:v[m])
        { 
            if(n!=f)
            { 
                DFS(f,m);
            }
        }
        del(c[m]);
    }
    void solve()
    { 
        int n;
        cin >> n;
        for(int i = 2, t;i <= n;i++)
        { 
            cin >> t;
            v[i].push_back(t);
            v[t].push_back(i);
        }
        for(int i = 1;i <= n;i++)
        { 
            cin >> c[i];
        }
        for(int i = 1;i <= n;i++)
        { 
            DFS(i,-1);
            ll ans1 = 0, ans2 = 0;
            for(int j = 1;j <= n;j++)
            { 
                ans1 = (ans1 + 1LL*p[j]*_1[j-1])%mod1;
                ans2 = (ans2 + 1LL*p[j]*_2[j-1])%mod2;
            }
            cout << ans1 << " " << ans2 << endl;
        }
        for(int i = 0;i <= n;i++)
        { 
            v[i].clear();
        }
        return;
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	cin.sync_with_stdio(0);
    	cin.tie(0);
    
    	init(maxn);
        int t;
        cin >> t;
        while(t--)
        { 
            solve();
        }
        return 0;
    }

# 1007 Increasing Subsequence DP #

题目地址[Increasing Subsequence][]  
题意：给一个序列，找到递增子序列的个数，子序列不能是其他递增子序列的子序列。  
思路：定义 dp\[i\] 为 a\[1…i\] 中以 a\[i\] 为结尾的极长上升子序列个数。则 dp\[i\] 对 dp\[j\] 有贡献当且仅当i 到 j 之间没有 a\[i\] 到 a\[j\] 之间的元素。dp\[i\] 初值为 1 当且仅当 a\[i\] 前面没有比 a\[i\] 小的。dp\[i\] 对答案有贡献当且仅当 a\[i\] 后面没有比 a\[i\] 大的。这样就有了一个朴素的 O ( n 2 ) O(n^2) O(n2)做法。  
通过分治并对两侧分别维护单调栈，我们可以把时间复杂度优化到 O ( n log ⁡ 2 n ) O(n \\log^2 n) O(nlog2n) 。  
当处理区间 \[l,r\] 时，令 m 为 \[l,r\] 的中点，对 a\[l,r\] 中所有元素按值依次从小到大处理。对 \[l,m\]和 \[m+1,r\] 分别建单调栈。左边单调栈中的元素值从小到大，位置从大到小。右边的单调栈中元素值从小到大，位置从小到大。处理左边的元素时直接往单调栈里丢，处理右边的元素 a\[i\] 时通过单调栈找到\[m+1,i-1\] 中比他小的最靠右侧的元素 a\[j\] 。然后在左侧的单调栈中找到比 a\[j\]大的第一个元素和比a\[i\]小的最后一个元素。区间 \[l,m\] 对dp\[i\]的贡献就来自单调栈里这两个元素之间的元素的dp值之和。  
AC代码：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef pair<int, int> pii;
    
    const int P = 998244353;
    int add(int a, int b) {  a += b; return a < P ? a : a - P; }
    int sub(int a, int b) {  a -= b; return a < 0 ? a + P : a; }
    
    const int N = 100001;
    int a[N], dp[N];
    
    void solve(int l, int r) { 
        if (l + 1 == r) return;
        int mid = (l + r) >> 1;
        solve(l, mid);
        vector<int> pos(r - l);
        iota(pos.begin(), pos.end(), l);//l是第一个值，后面的值由前一个值+1得来
        sort(pos.begin(), pos.end(), [&](int i, int j) {  return a[i] < a[j]; });//根据a[i]a[j]的升序对ij进行排序
        vector<int> ls, rs;//左栈和右栈
        vector<int> sum(1, 0);
        for (int i : pos) { 
            if (i < mid) { //左侧单调栈
                while (!ls.empty() && ls.back() < i)//维护ls单调栈，ls存的是下标
                    sum.pop_back(), ls.pop_back();
                ls.push_back(i);
                sum.push_back(add(sum.back(), dp[i]));
            }
            else { 
                while (!rs.empty() && rs.back() > i)
                    rs.pop_back();
                if (ls.empty()) continue;
                int id1 = partition_point(ls.begin(), ls.end(), [&](int x) {  return a[x] < a[i]; }) - ls.begin();//partition_point返回根据一定规则将分好组的数据的分界位置
                int id2 = rs.empty() ? 0 : partition_point(ls.begin(), ls.end(), [&](int x) {  return a[x] < a[rs.back()]; }) - ls.begin();
                dp[i] = add(dp[i], sub(sum[id1], sum[id2]));
                rs.push_back(i);
            }
        }
        solve(mid, r);
    }
    
    int main(void) { 
        freopen("in.txt","r",stdin);
        int T; scanf("%d", &T);
        while (T--) { 
            int n; scanf("%d", &n);
            for (int i = 1; i <= n; ++i)
                scanf("%d", &a[i]);
            for (int i = 1, v = INT_MAX; i <= n; ++i) { //初始化dp，如果a[i]前面有比他小的值dp[i]=0;否则等于1
                if (v > a[i])
                    dp[i] = 1;
                else
                    dp[i] = 0;
                v = min(v, a[i]);
            }
            solve(1, n + 1);
            int ans = 0;
            for (int i = n, v = 0; i >= 1; --i) { 
                if (v < a[i])
                    ans = add(ans, dp[i]);
                v = max(v, a[i]);
            }
            printf("%d\n", ans);
        }
        return 0;
    }

# 1008 Lawn of the Dead 线段树 #

题目地址【[1008 Lawn of the Dead][]】  
题意：一个地图，只能向右或向下移动，有些点不能到达，问能到达的点有多少个  
思路：考虑所有点的个数减去不能到达的点的个数，即为可以到达的点的个数。根据题意，有地雷的地方是不可以到达的。由于僵尸只会向右和向下走，当某个点的左边和上方都不可达时，该点不可达，并会对自己右边的点和下方的点造成影响。由于空间很大但地雷数有限，可以从上往下逐行对每一行的地雷排序后进行处理。对每个地雷，找到从自己的右上角点（x-1，y+1）开始的从左往右的连续不可达区域的范围，那么x这行的这个范围也  
不可达。可以用线段树来实现区间查询和区间覆盖。每一行处理完后查询该行不可达的点数，累加后用总点数减即得到答案。

#include<bits/stdc++.h>
    using namespace std;
    #define ls (x<<1)
    #define rs (x<<1|1)
    const int N = 1e5 + 5;
    const int inf = 0x3f3f3f3f;
    vector<int>e[N];
    int tr[2][N << 2], lz[2][N << 2];//线段树，区间更新的懒标记
    
    //f表示二维数组的行，x是线段树当前结点编号
    void push_down(int f, int x, int l, int r, int mid) { 
    	if (lz[f][x] == -1)return;
    	tr[f][ls] = lz[f][x] * (mid - l + 1);
    	tr[f][rs] = lz[f][x] * (r - mid);
    	lz[f][ls] = lz[f][rs] = lz[f][x];
    	lz[f][x] = -1;
    }
    //x线段树当前结点编号，l r当前结点区间，L R是操作区间
    void update(int f,int x, int l, int r, int L, int R, int v) { 
    	if (L <= l && R >= r) { 
    		tr[f][x] = (r - l + 1) * v;
    		lz[f][x] = v;
    		return;
    	}
    	int mid = (l + r) >> 1;
    	push_down(f, x, l, r, mid);
    	if (R <= mid)update(f, ls, l, mid, L, R, v);
    	else if (L > mid)update(f, rs, mid + 1, r, L, R, v);
    	else { 
    		update(f, ls, l, mid, L, mid, v);
    		update(f, rs, mid + 1, r, mid + 1, R, v);
    	}
    	tr[f][x] = tr[f][ls] + tr[f][rs];	//向上更新
    }
    int query(int f, int x, int l, int r, int L, int R) { 
    	if (!tr[f][x])return inf;
    	if (l == r)return l;
    	int mid = l + r >> 1;
    	push_down(f, x, l, r, mid);
    	if (L <= l && R >= r) { 
    		if (tr[f][ls] > 0) return query(f, ls, l, mid, l, mid);
    		else return query(f, rs, mid + 1, r, mid + 1, r);
    	}
    	else { 
    		if (R <= mid)return query(f, ls, l, mid, L, R);
    		else if (L > mid)return query(f, rs, mid + 1, r, L, R);
    		else return min(query(f, ls, l, mid, L, mid), query(f, rs, mid + 1, r, mid + 1, R));
    	}
    }
    int main() { 
    	int T;
    	scanf("%d", &T);
    	while (T--) { 
    		int n, m, k;
    		scanf("%d %d %d", &n, &m, &k);
    		for (int i = 1; i <= n; ++i)e[i].clear();
    		for (int i = 1; i <= (m << 2); ++i) { 
    			tr[0][i] = tr[1][i] = 0;//初始化线段树，记录的是相邻两行陷阱数量。
    			lz[0][i] = lz[1][i] = -1;//懒标记
    		}
    		for (int i = 0; i < k; ++i) { 
    			int x, y;
    			scanf("%d %d", &x, &y);
    			e[x].push_back(y);//对应某一行的不能到达的点纵坐标
    		}
    		long long ans = 0;
    		update(0, 1, 1, m, 1, 1, 1);//线段树区间更新，加v。
    		for (int x = 1; x <= n; ++x) { 
    			int l = 0;
    			sort(e[x].begin(), e[x].end());
    			for (auto& y : e[x]) { 
    				if (y - 1 >= l + 1) { 
    					int pos = query((x & 1) ^ 1, 1, 1, m, l + 1, y - 1);
    					if (pos != inf)update(x & 1, 1, 1, m, pos, y - 1, 1);
    				}
    				l = y;
    			}
    			if (l + 1 <= m) { 
    				int pos = query((x & 1) ^ 1, 1, 1, m, l + 1, m);
    				if (pos != inf)update(x & 1, 1, 1, m, pos, m, 1);
    			}
    			ans += tr[x & 1][1];
    			update((x & 1) ^ 1, 1, 1, m, 1, m, 0);
    		}
    		printf("%lld\n", ans);
    	}
    	return 0;
    }

# 1009 License Plate Recognition 思维 #

[1009 License Plate Recognition][]  
题意：给一个字符矩阵，上面的字符组成一个车牌号，让输出车牌号的最左端和最右端所在的列。  
思路：不太会说，直接上代码

#include <iostream>
    #include <bits/stdc++.h>
    
    #define inf 0x3f3f3f3f
    #define mod 1000000007
    #define lmax 1000
    #define pi 3.141592653589793238462643383279
    #define eps 1e-7
    
    using namespace std;
    typedef long long ll;
    typedef double type;
    int biao[103];
    int ce[103];
    
    int main()
    { 
        int t;
        scanf("%d",&t);
        for(int k=1; k<=t; k++)
        { 
            char ch;
            memset(biao,0,sizeof(biao));
            for(int i=1; i<=30; i++)
            { 
                for(int j=1; j<=100; j++)
                { 
                    scanf(" %c",&ch);
                    //cin>>ch;
                    if(ch=='#')
                        biao[j]++;
                }
            }
            int i=1;
            int cex=1;
            while(i<=100)
            { 
                while(i<=100)
                { 
                    if(biao[i]==0)
                    { 
                        i++;
                    }
                    else
                    { 
                        ce[cex]=i;
                        cex++;
                        i++;
                        break;
                    }
                }
                while(i<=100)
                { 
                    if(biao[i]==0)
                    { 
                        ce[cex]=i-1;
                        i++;
                        cex++;
                        break;
                    }
                    else
                    { 
                        i++;
                    }
                }
            }
            if(cex==15)
            { 
                printf("Case #%d:\n",k);
                for(int j=1; j<cex; j+=2)
                { 
                    printf("%d %d\n",ce[j],ce[j+1]);
                }
            }
            else
            { 
                int kk=cex-14;
                printf("Case #%d:\n",k);
                printf("%d %d\n",ce[1],ce[kk+1]);
                for(int j=kk+2; j<cex; j+=2)
                { 
                    printf("%d %d\n",ce[j],ce[j+1]);
                }
            }
        }
        return 0;
    }

[2021_MINIEYE_4]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A84%A3%A9&source=1&searchmode=source
[2021_MINIEYE_4 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=987
[1001 Calculus]: https://acm.hdu.edu.cn/showproblem.php?pid=6985
[1002 Kanade Loves Maze Designing]: https://acm.hdu.edu.cn/showproblem.php?pid=6986
[07cea4d299f246f98927c9b680deb506.png]: /images/20220829/eea93d7b062248448a43a04e0bafaba6.png
[Increasing Subsequence]: https://acm.hdu.edu.cn/showproblem.php?pid=6991
[1008 Lawn of the Dead]: https://acm.hdu.edu.cn/showproblem.php?pid=6992
[1009 License Plate Recognition]: https://acm.hdu.edu.cn/showproblem.php?pid=6993