“高教社杯”第三届福建省大学生程序设计竞赛

Tag Pro.ID Problem Title Ratio(AC/Submit)

	1	Solve equation	48.47%(111/229)
	2	Bin & Jing in wonderland	14.29%(4/28)
	3	Floor problem	88.67%(133/150)
	4	Digits Count	17.19%(11/64)
	5	How many tuples	0.00%(0/0)
	6	Hua Rong Dao	33.33%(22/66)
	7	Mod problem	20.69%(6/29)
	8	Mountain Number	28.57%(2/7)
	9	Star	24.38%(78/320)
	10	Min Number	32.57%(85/261)
	11	Tickets	28.00%(14/50)

1、水题

#include <stdio.h>
#include <string.h>
const int N = 105;

int t, base, n1, n2;
char num1[N], num2[N];

int tra(char *s) {
    int ans = 0;
    for (int i = 0; i < strlen(s); i ++) {
	if (s[i] >= '0' && s[i] <= '9')
	    ans = ans * base + s[i] - '0';
	else
	    ans = ans * base + s[i] - 'a' + 10;
    }
    return ans;
}

void init() {
    scanf("%s%s%d", num1, num2, &base);
    n1 = tra(num1); n2 = tra(num2);
}

void solve() {
    printf("(%d,%d)\n", n1 / n2, n1 - n1 / n2 * n2);
}

int main() {
    scanf("%d", &t);
    while (t--) {
	init();
	solve();
    }
    return 0;
}

第二题:组合概率

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define min(a,b) (a)<(b)?(a):(b)
const int N = 55;
typedef long long ll;

double c[N][N];
int t, n, k, r, res[N], Minr, vis[N];
double p[N], pr, pMax;

double C(int n, int m) {
    double ans = 1.0;
    m = min(m, n - m);
    for (int i = 0; i < m; i ++)
	ans = ans * (n - i) / (i + 1);
    return ans;
}
void c_table() {
    for (int i = 0; i <= 52; i ++)
	for (int j = 0; j <= i; j ++)
	    c[i][j] = C(i, j);
}

void init() {
    pMax = 1.0;
    memset(vis, 0, sizeof(vis));
    scanf("%d%d%d", &n, &k, &r);
    for (int i = 1; i <= n; i ++)
	scanf("%lf", &p[i]);
    for (int i = 0; i < r; i ++) {
	scanf("%d", &res[i]);
	pMax *= p[res[i]];
	vis[res[i]] ++;
    }
    sort(res, res + r);
    Minr = res[0];
    pr = 0.0;
    for (int i = 1; i < Minr; i ++)
	pr += p[i];
}

void fuck(double &s) {
    int kk = k;
    for (int i = 0; i <= n; i ++) {
	s *= c[kk][vis[i]];
	kk -= vis[i];
    }
}


double sb(double p, int k) {
    double ans = 1.0;
    for (int i = 0; i < k; i ++)
	ans *= p;
    return ans;
}

double solve() {
    double ans = 0;
    double s;
    for (int i = 0; i <= k - r; i ++) {
	vis[0] = k - r - i;
	s = pMax * sb(pr ,k - r - i) * sb(p[Minr], i);
	fuck(s);
	ans += s;
	vis[Minr] ++;
    }
    return ans;
}

int main() {
    c_table();
    scanf("%d", &t);
    while (t--) {
	init();
	printf("%.6lf\n", solve());
    }
    return 0;
}

第三题：水题

#include <stdio.h>
#include <string.h>

int t, n, l, r;
int main() {
    scanf("%d", &t);
    while (t--) {
	scanf("%d%d%d", &n, &l, &r);
	int sum = 0;
	for (int i = l; i <= r; i ++)
	    sum += n / i;
	printf("%d\n", sum);
    }
    return 0;
}

第四题:应该是线段树，没出。

第五题：看都没看

第六题：搜索dfs

#include <stdio.h>
#include <string.h>

const int block[3][3][2] = {{{0, 0}, {0, 1}, {0, 0}}, {{0, 0}, {1, 0}, {0, 0}}, {{0, 0}}};
const int blockn[3] = {2, 2, 1};

int t, n, vis[5][5], save[5], ans;

bool judge(int x, int y, int i, int n) {
    for (int j = 0; j < blockn[i]; j ++) {
	int xx = x + block[i][j][0];
	int yy = y + block[i][j][1];
	if (xx < 0 || xx >= n || yy < 0 || yy >= 4 || vis[xx][yy]) {
	    return false;
	}
    }
    return true;
}
void dfs(int x, int y, int n, int num) {
    if (num == n * 4) {
	ans ++;
	return;
    }
    if (y == 4) dfs(x + 1, 0, n, num);
    if (vis[x][y]) dfs(x, y + 1, n, num);
    for (int i = 0; i < 3; i ++) {
	if (judge(x, y, i, n)) {
	    for (int j = 0; j < blockn[i]; j ++)
		vis[x + block[i][j][0]][y + block[i][j][1]] = 1;
	    dfs(x, y + 1, n, num + blockn[i]);
	    for (int j = 0; j < blockn[i]; j ++)
		vis[x + block[i][j][0]][y + block[i][j][1]] = 0;
	}
    }
}

int solve(int n) {
    int an = 0;
    for (int i = 0; i < n - 1; i ++)
	for (int j = 0; j < 3; j ++) {
	    memset(vis, 0, sizeof(vis));
	    vis[i][j] = vis[i + 1][j] = vis[i][j + 1] = vis[i + 1][j + 1] = 1;
	    ans = 0;
	    dfs(0, 0, n, 4);
	    an += ans;
	}
    return an;
}

int main() {
    for (int i = 1; i <= 4; i ++)
	save[i] = solve(i);
    scanf("%d", &t);
    while (t--) {
	scanf("%d", &n);
	printf("%d\n", save[n]);
    }
    return 0;
}

第七题；没看

第八题：应该是数位DP，没出。

第九题：暴力枚举+几何

#include <stdio.h>
#include <string.h>

typedef long long ll;
const int N = 105;

int t, n;
struct point {
    ll x, y;
} p[N];

void init() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
	scanf("%lld%lld", &p[i].x, &p[i].y);
}

bool judge(int i, int j, int k) {
    return (p[j].x - p[i].x) * (p[k].x - p[i].x) + (p[j].y - p[i].y) * (p[k].y - p[i].y) > 0;
}

int solve() {
    int ans = 0;
    for (int i = 0; i < n; i ++)
	for (int j = i + 1; j < n; j ++)
	    for (int k = j + 1; k < n; k ++) {
		if (judge(i, j, k) && judge(j, i, k) && judge(k, i, j))
		    ans ++;
	    }
    return ans;
}

int main() {
    scanf("%d", &t);
    while (t--) {
	init();
	printf("%d\n", solve());
    }
    return 0;
}

第十题：贪心

#include <stdio.h>
#include <string.h>

const int N = 1005;

int t, m;
char n[N];

void init() {
    scanf("%s%d", n, &m);
}

void swap(char &a, char &b) {
    char c = a;
    a = b;
    b = c;
}

void solve() {
    if (m != 0) {
	int len = strlen(n), Min = 10, Min_v = len, start = 1, mm = 0;
	for (int i = len - 1; i > 0; i --)
	    if (Min > n[i] - '0' && n[i] != '0') {
		Min = n[i] - '0';
		Min_v = i;
	    }
	if (Min < n[0] - '0') {
	    swap(n[0], n[Min_v]);
	    mm ++;
	}
	while (start != len && mm != m) {
	    Min = 10;
	    for (int i = len - 1; i > start; i --)
		if (Min > n[i] - '0') {
		    Min = n[i] - '0';
		    Min_v = i;
		}
	    if (Min < n[start] - '0') {
		swap(n[start], n[Min_v]);
		mm ++;
	    }
	    start ++;
	}
    }
    printf("%s\n", n);
}

int main() {
    scanf("%d", &t);
    while (t--) {
	init();
	solve();
    }
    return 0;
}

第十一题：并查集+欧拉回路

#include <stdio.h>
#include <string.h>

const int N = 100005;

int t, n, m, vis[N], parent[N], d[N], s[N], sn, v[N], num[N];

int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}

void init() {
    scanf("%d%d", &n, &m);
    sn = 0;
    for (int i = 0; i <= n; i ++)
	parent[i] = i;
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
    memset(v, 0, sizeof(v));
    memset(num, 0, sizeof(num));
    int a, b;
    while (m--) {
	scanf("%d%d", &a, &b);
	vis[a] = 1; vis[b] = 1;
	d[a] ++; d[b] ++;
	int pa = find(a), pb = find(b);
	if (pa != pb)
	    parent[pa] = pb;
    }
}


int solve() {
    int ans = 0;
    for (int i = 1; i <= n; i ++) {
	if (vis[i]) {
	    int pi = find(i);
	    if (!v[pi]) {
		v[pi] = 1;
		s[sn ++] = pi;
		if (d[i] % 2) num[pi] ++;
	    }
	    else {
		if (d[i] % 2)
		    num[pi] ++;
	    }
	}
    }
    for (int i = 0; i < sn; i ++) {
	ans += num[s[i]] / 2 - 1;
    }
    ans += sn - 1;
    return ans;
}

int main() {
    scanf("%d", &t);
    while (t--) {
	init();
	printf("%d\n", solve());
    }
    return 0;
}