1013考试 乱搞 Tarjan找环 概率DP

1013考试总结

T1

​ 题目大意:

​ 给定\(n\)个字符串,都是小写字母,现在要把它们缩短,要求如下:

​ 1.缩短后的长度一定要小于缩短前的长度。

​ 2.缩短后都是小写字母。

​ 3.相同的字符串缩短完也相同,不同的字符串缩短后一定不同。

​ \(n <= 1000\)

​ 乱搞吧。

​ 考场上的想法是先把最后一个字符删去,如果与前面有冲突的就\(rand\)一个\(x\),代表第\(x\)位要修改。因为判冲突的复杂度比较玄,rand好了就很快,rand不好就凉了,最后T了一个点。

​ 比较正确的思路是:重构所有的字符串只要他们都合法就行。先把所有的字符串按长度排个序。因为\(n <= 1000\),所以我们最多需要三位的字符串就够了。开三个变量\(a, b, c\),范围都是从96到122,也就是小写字母的ASCLL码值。每次碰见一个新字符串就让\(c ++\),如果\(c == 123\),就类似于进位,让\(b ++\),\(c = 96\)。\(a\)也同理。时间复杂度\(O(n log n)\)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;
int n, aa, ab, ac;
map <string, int> mp;
struct node { string s; int id, len, last, a, b, c; } a[N];

int cmp(node a, node b) { return a.len < b.len; }

int mmp(node a, node b) { return a.id < b.id; }

int main() {

    cin >> n; ac = 96;
    for(int i = 1;i <= n; i++) {
        cin >> a[i].s;
        a[i].len = a[i].s.length();
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1;i <= n; i++) {
        if(mp[a[i].s]) { 
            a[i].last = mp[a[i].s];
            a[i].a = a[a[i].last].a;
            a[i].b = a[a[i].last].b;
            a[i].c = a[a[i].last].c;
            continue;
        }
        mp[a[i].s] = i; ac ++;
        if(ac == 123) {
            if(ab == 0) ab = 96;
            else ab ++;
            ac = 96;
        }
        if(ab == 123) {
            if(aa == 0) aa = 96;
            else aa ++;
            ab = 96;
        }
        a[i].a = aa; a[i].b = ab; a[i].c = ac;
    }
    sort(a + 1, a + n + 1, mmp);
    for(int i = 1;i <= n; i++) {
        if(a[i].a) cout << (char) a[i].a;
        if(a[i].b) cout << (char) a[i].b;
        if(a[i].c) cout << (char) a[i].c;
        cout << "\n";
    }

    fclose(stdin); fclose(stdout);
    return 0;
}

T2

​ 题目大意:

​ 给定\(n\)个点和\(n\)条有向边,删一条边后使得只有一个点没有出度,其他所有点只有一个出度,输出删的这条边最大的编号。

​ 考试的时候其实已经和正解想法差不多了,但还是一些细节没想到。

​ 考试时的想法是分两种情况:1.如果有一个点有两个出度,那肯定是删这两条边编号大的那个。2.如果有环,删除这个环上编号最大的那一条边。

​ 但只拿了80pts。

​ 错误的地方是:1.第一种情况能删的边一定是可以从根节点到达的那条边,根节点是指出度为0的点。2.我用拓扑找的环,但是拓扑只可以判断图中是否又换,却不可以确定某个点是否真的在环上,所以得用\(Tarjan\)找环。

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 1e6 + 5;
int n, p, t, cnt, tag, ans, tot, top;
int in_edge[N], head[N], vis[N], low[N], dfn[N], sta[N], in[N], zhi[N], tt[N];
struct edge { int u, to, id, nxt; } e[N];
priority_queue <int> q;

void add(int x, int y, int i) {
    e[++ cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; e[cnt].id = i; e[cnt].u = x;
    in_edge[y] ++; zhi[y] = i; 
}

void dfs(int x) {
    vis[x] = 1;
    for(int i = head[x]; i ; i = e[i].nxt) {
        int y = e[i].to; if(y == t) continue;
        dfs(y);
    }
}

void Tarjan(int now){
	low[now] = dfn[now] = ++ tot; sta[++ top] = now; in[now] = 1;
	for(int i = head[now]; i; i = e[i].nxt){
		int to = e[i].to;
		if(!dfn[to]){
			Tarjan(to); low[now] = min(low[now], low[to]);
		}else if(in[to]) low[now] = min(low[now], dfn[to]);
	}
	if(dfn[now] == low[now]){
		int x = sta[top], y = now;
		do{
			x = sta[top --];
			q.push(zhi[x]);
			in[x] = 0;
		}while(x != y);
		if(q.size() > 1) ans = max(ans, q.top());
		while(q.size()) q.pop();
	}
}

int main() {
 
    n = read();
    for(int i = 1, x, y;i <= n; i++) x = read(), y = read(), add(x, y, i);
    for(int i = 1;i <= n; i++) {
        if(in_edge[i] > 1) { tag = 1; t = i; }
        if(!in_edge[i]) { p = i; }
    }
    if(tag) { 
        for(int i = 1; i <= n; i ++){
			if(e[i].to == t) tt[++ tot] = i;
		}
		dfs(p);
		if(vis[e[tt[1]].u] == 0) ans = tt[1];
		else{
			if(vis[e[tt[2]].u] == 0) ans = tt[2];
			else ans = max(tt[1], tt[2]);
		}
    }
    else {
        for(int i = 1;i <= n; i++) if(!dfn[i]) Tarjan(i); 
    }
    printf("%d", ans);

    fclose(stdin); fclose(stdout);
    return 0;
}

T3

​ 题目大意:

​ 有两个人\(A, B\),两个数\(n, k\)。\(n\)代表每个人有\(n\)吨茶,\(k\)表示\(A\)每次可以倒出\(4k, 3k, 2k, k\)吨茶,那么\(B\)倒出的茶与\(A\)相加为\(5k\),也就是说\(A\)倒出\(4k\),\(B\)就倒出\(k\)。问\(A\)比\(B\)先到完加上同时倒完的概率是多少。\(n, k <= 1e9\)

​ 考场上完全不会。。。

​ 首先可以写出\(n ^ 2\)暴力:

​ \(f[i][j]\)表示\(A\)倒出\(i * k\)吨,\(B\)倒出\(j * k\)吨的概率,那么dp转移方程可以写出:\(f[min(n, i + l * k)][min(n, j + (4 - l) * k)] += 1.0 / 4.0 * f[i][j]\)。

​ 然后打个表,发现\(n >= 300\)的都会输出1.000000。诶嘿嘿嘿暴力变正解,直接\(n ^ 2\)做就好拉。

#include <bits/stdc++.h>
    
using namespace std;
    
inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}
    
const int N = 2005;
int n, k;
double ans, f[N][N];

int main() {

    n = read(); k = read();
    if(n / k > 2000) { printf("1.000000"); return 0; }
    int tmp = n / k; if(n % k) tmp ++;
    n = tmp; k = 1; f[0][0] = 1;
    for(int i = 0;i < n; i++) 
        for(int j = 0;j < n; j++) 
            for(int l = 1;l <= 4; l++) 
                f[min(n, i + l * k)][min(n, j + (4 - l) * k)] += 1.0 / 4.0 * f[i][j];
    for(int j = 0;j < n; j++) ans += f[n][j];
    ans += f[n][n] / 2.0;
    printf("%.6lf", ans);

    fclose(stdin); fclose(stdout);
    return 0;
}
上一篇:Tarjan算法分解强连通分量(附详细参考文章)


下一篇:2-SAT (two-statisfiability) 算法 学习笔记