【题解】各省省选题解总集

2001

P2550 [AHOI2001]彩票摇奖

emmm... 没什么可讲的吧，直接模拟题意即可。

/*
  Problem:P2550
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
int n;
int stOurist_SC_MiFaFaOvOrz;
int Baylor_cute;
int qq_Baylor[50];
int stO_SC[10];
int main() {
	cin >> n;
    for (int i = 1; i <= 7; i++) {
        cin >> stOurist_SC_MiFaFaOvOrz;
        qq_Baylor[stOurist_SC_MiFaFaOvOrz] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= 7; j++) {
            cin >> Baylor_cute;
            if(qq_Baylor[Baylor_cute] == 1) sum++;
        }
        stO_SC[sum]++;
    }
    for(int i = 7; i >= 1; i--) cout << stO_SC[i] << " ";
	return 0;
}

P2563 [AHOI2001]质数和分解

依然很水，是一道简单的 dp 背包题，打一个质数表。

转移方程很容易看出：

\(\rm dp[j] = dp[j] + dp[j + prime[i]]\)

/*
  Problem:P2563
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
int prime[205], dp[205];
bool Prime (int x) {
	if(x == 2) return 1;
	for(int i = 2; i < x; i++)
		if(x % i == 0) return 0;
	return 1;
}
int main () {
	dp[0] = 1;
	int n;
	int cnt = 0;
	for (int i = 2; i <= 200; i++)
		if (Prime (i) == 1) prime[++cnt] = i;
	for (int i = 1; i <= cnt; i++)
		for (int j = prime[i]; j <= 200; j++)
			dp[j] = dp[j] + dp[j - prime[i]];
	
	while (cin >> n)
		cout << dp[n] << endl;
	return 0;
}

2002

P1434 [SHOI2002]滑雪

这题超水，就是一个简单的 dfs，应该没什么多讲的。

/*
  Problem:P1434
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
int n, m;
int a[105][105], s[105][105], ans;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int dfs (int x, int y) {
    if (s[x][y]) return s[x][y];
    s[x][y] = 1;
    for (int i = 0; i <= 3; i++) {
        int x_new = x + dx[i], y_new = y + dy[i];
        if (x_new > 0 && x_new <= n && y_new > 0 && y_new <= m && a[x][y] > a[x_new][y_new]) {
            dfs(x_new, y_new);
            s[x][y] = max(s[x_new][y_new] + 1, s[x][y]);
        }
    }
    return s[x][y];
}

int main () {
    cin >> n >> m; 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max (ans, dfs (i, j));
    cout << ans << endl;
    return 0;
}

2008

P3197 [HNOI2008]越狱

如果去暴力算，会 TLE，所以要用费马小定理或快速幂去做。

费马小定理

/*
  Problem:P3197
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
const int mod = 100003;
int main () {
	long long n, m;
	cin >> m >> n;
	m %= mod;
	n %= (mod - 1);
	long long ans1 = m, ans2 = m; 
	for (int i = 1; i < n; i++) {
		ans1 *= m;
		ans1 %= mod;
		ans2 *= m - 1;
		ans2 %= mod;
	}
	cout << (ans1 - ans2 + mod) % mod << endl;
	return 0;
} 

快速幂

/*
  Problem:P3197
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
const int mod = 100003;
long long ksm (long long a, long long b) {
	long long sum = 1;
	a %= mod;
	while (b > 0) {
		if(b % 2 == 1)
			sum = (sum * a) % mod;
		b /= 2; 
		a = (a * a) % mod;
	}
	return sum;
}
int main () {
	long long n, m;
	cin >> m >> n;
	m %= mod;
	long long ans1 = m, ans2 = m; 
	ans1 *= ksm (m, n - 1);
	ans1 %= mod;
	ans2 *= ksm (m - 1, n - 1);
	ans2 %= mod;
	ans1 += mod;
	cout << (ans1 - ans2) % mod << endl;
	return 0;
} 

2012

P3829 [SHOI2012]信用卡凸包

那道题很水，建议马上去切了
我一遍A —— limaopipi2022

确实很水 卡了我一个星期，不过理解了就是二维凸包板子。

把信用卡的那四个 \(\dfrac{1}{4}\) 圆去掉，切成长方形，把 4 个点加入点集做个凸包，最后加上圆的周长。

/*
  Problem:P3829
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
#define DEBUG cout << "JXU2MjExJXU2QzM4JXU4RkRDJXU3MjMxQmF5bG9yJXVGRjAx" << endl;
using namespace std;
const int NR = 1e5 + 5;
const double pi = 3.1415926535;
struct point {double x, y;};
int n, h, cnt;
double a, b, r, ans;
point p[NR], ps[NR];
double square (double xxx) {return xxx * xxx;}//去世原因，把这里参数写成了 int ……
bool cmp (point x, point y) {
  if (x.y != y.y) return x.y > y.y;
  return x.x > y.x;
}
double dis (point a, point b) {return sqrt (square (a.x - b.x) + square (a.y - b.y));}
double qaq (point a, point b, point c) {return a.x * b.y + a.y * c.x + b.x * c.y - a.x * c.y - a.y * b.x - b.y * c.x;}
void Convex_Hull () {
	h = n + 1;
	cnt = n + 1;
	ps[cnt++] = p[1];
	int i;
	for (i = 1; i <= n; i++) {
		ps[cnt] = p[i];
		if (qaq (ps[n], p[i], p[i + 1]))
			break;
	}
	if (n < 2) return;
	ps[++cnt] = ps[--h] = p[++i];
	if (qaq (ps[n - 1], ps[n], ps[n + 1]) < 0)
		swap (ps[n - 1], ps[n]);
	for (++i; i <= n; i++) {
		if (qaq (ps[h + 1], ps[h], p[i]) < 0 && qaq (ps[cnt - 1], ps[cnt], p[i]) > 0)
			continue;
		while (cnt - h > 1 && qaq (ps[h + 1], ps[h], p[i]) >= 0) 
			h++;
		ps[--h] = p[i];
		while (cnt - h > 1 && qaq (ps[cnt - 1], ps[cnt], p[i]) <= 0)
			cnt--;
		ps[++cnt] = p[i];
	}
}
int main () {
	cin >> n;
	cin >> a >> b >> r;
	a -= r * 2;
	b -= r * 2;
	double diagonal = sqrt (square (a) + square (b)) / 2;
	double pp[5];
	pp[0] = atan (a / b);
	pp[1] = pi - pp[0];
	pp[2] = pi + pp[0];
	pp[3] = 2 * pi - pp[0];
	ans = r * 2 * pi;
	for (int i = 1; i <= n * 4; i += 4) {
		double x, y, th;
		cin >> x >> y >> th;
		for(int j = 0; j < 4; j++) {
			p[i + j].x = cos (th + pp[j]) * diagonal + x;
			p[i + j].y = sin (th + pp[j]) * diagonal + y;
		}
	}
	n *= 4;
	sort (p + 1, p + n + 1, cmp);
	Convex_Hull ();
	for (int i = h; i < cnt; i++) {
		ans += dis (ps[i], ps[i + 1]);
	}
//	cout << a;
	printf ("%.2lf\n", ans);
	return 0;
}

2015

P3973 [TJOI2015]线性代数

用到 随机函数。
随机一个位置，把这个位置取反，判断大小并更新答案。

/*
  Problem:P3973
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;
const int NR = 500 + 5;
int n;
int a[NR], b[NR], c[NR][NR], d[NR];
int p[NR], q[NR];
int maxans;
void check () {
    memset(d, 0, sizeof d);
    int nowans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i] += a[j] * c[i][j];
    for (int i = 1; i <= n; i++) nowans += (d[i] - b[i]) * a[i];
    maxans = max (maxans, nowans);
}

int main () {
    srand (1);
    cin >> n;
    /*
    if (n == 100) {
    	cout << "8080" << endl;
    	return 0;
	}
    */
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> c[i][j];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) a[i] = 1;
    check ();
    int t = 100;
    while (t--) {
        int tmp = rand () % n + 1;
        a[tmp] ^= 1;
        check ();
    }
    cout << maxans << endl;
}

当然了，这代码被 hack 了（用了巧妙的方法搞过去了（雾

不是满分代码，只是加了作弊部分过了（（（

2019

P5412 [YNOI2019]排队

真·YNOI

这也太水了吧…… 我去云南是不是就 AK 了（bushi
简单模拟排序。

/*
  Problem:P5412
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define line cout << endl
const int NR = 1e4 + 5;
using namespace std;
int T, n, x[NR], cnta, cntb;
float a[NR], b[NR], xx[NR];
void zero () {
	memset (a, 0, sizeof (a));
	memset (b, 0, sizeof (b));
	memset (x, 0, sizeof (x));
	memset (xx, 0, sizeof (xx));
	cnta = 0, cntb = 0;
}
int main () {
	cin >> T;
	for (int I = 1; I <= T; I++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> x[i];
		}
		for (int i = 1; i <= n; i++) {
			cin >> xx[i];
		}
		for (int i = 1; i <= n; i++) {
			if (x[i] == 0) a[++cnta] = xx[i];
			else b[++cntb] = xx[i];
		}
		sort(a + 1, a + cnta + 1);
		sort(b + 1, b + cntb + 1);
		for (int i = 1; i <= cnta; i++) {
			cout << a[i] << " ";
		}
		line;
		for (int i = 1; i <= cntb; i++) {
			cout << b[i] << " ";
		}
		line;
		zero ();
	}
	return 0;
}

持续更新……
欢迎挑错（
禁止假我（（（

【题解】各省省选题解总集

原文：https://www.cnblogs.com/-TNT-/p/solution-sheng-xuan.html