A
签到
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define IO ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 1e5 + 5;
int n, m, _, k;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
while (cin >> n && n) {
++_;
m += n;
k = m / 50;
m %= 50;
if (k == 1) cout << "Input #" << _ << ": Sweet!
" ;
else if (k >= 2) cout << "Input #" << _ << ": Totally Sweet!
" ;
}
return 0;
}
B
签到
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define pb push_back
using namespace std;
const int N = 1e5 + 5;
int n, m, _, k;
vector<string> vs[21];
string s;
bool check(string s, string t) {
rep (i, 0, s.length() - 1)
if (t[i] != '-' && t[i] != s[i])
return false;
return true;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
rep (i, 1, n) cin >> s, vs[s.length()].pb(s);
cin >> m;
rep (i, 1, m) {
cin >> s;
cout << "Word #" << i << ": " << s << '
';
int tot = 0;
for (string t : vs[s.length()])
if (check(t, s)) {
++tot;
cout << t << '
';
}
cout << "Total number of candidate words = " << tot << '
' << endl;
}
return 0;
}
C
签到
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef double db;
const int N = 1e5 + 5;
int n, m, _, k;
int a[5], b[5];
void work(int c) {
a[(c - 1 + 5) % 5] += a[c];
a[(c + 1) % 5] += a[c];
a[c] = -a[c];
}
bool cmp(int x, int y) {
return a[x] < a[y];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
rep(i, 0, 4) b[i] = i;
for (cin >> _; _; --_) {
rep(i, 0, 4) cin >> a[i];
while (1) {
sort(b, b + 5, cmp);
//cout << a[b[0]] << ' ' << b[0] << '
';
if (a[b[0]] >= 0) break;
work(b[0]);
}
cout << "Pentagon #" << ++k << ":
";
cout << a[0];
rep(i, 1, 4) cout << ' ' << a[i];
cout << '
';
if (_ != 1) cout << '
';
}
return 0;
}
D
签到
#include <bits/stdc++.h>
#define ed "
"
#define fi first
#define se second
#define SZ size()
#define ll long long
#define V(a) vector <a>
#define P pair <int,int>
#define PB(a) push_back(a)
#define MK(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define each(a,b) for(auto (a):(b))
#define T(t) int t;cin >> t;while(t--)
#define MSET(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
#define debug(x) cout << "debug:" << x << endl;
#define close ios::sync_with_stdio(false),cin.tie(NULL);
using namespace std;
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b){ return a*b/gcd(a,b); }
ll ksm(ll a,ll b,ll mod){ll ans=1;while(b){if(b&1)ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return (ans)%mod;}
template <typename _tp> inline _tp read(_tp&x){
char ch=getchar(),sgn=0;x=0;
while(ch^'-'&&!isdigit(ch))ch=getchar();if(ch=='-')ch=getchar(),sgn=1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(sgn)x=-x;return x;
}
int main(){
int cnt = 0;
T(t){
cnt++;
string s,s1,s2;cin >> s;
bool flag = false;
for(int i = 1;i < (int)s.size();i++){
s1 = s.substr(0,i);
s2 = s.substr(i,(int)s.size()-i);
int x = atoi(s1.c_str());
int y = atoi(s2.c_str());
if(gcd(x,y)==1){
cout << "Ticket #" << cnt << ":" << ed << x << " " << y << ed << ed;
flag = true;break;
}
}
if(!flag) cout << "Ticket #" << cnt << ":" << ed << "Not relative" << ed << ed;
}
return 0;
}
E
dp, 模型传纸条
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 1e2 + 5;
int n, m, _, k, t;
int s[N][N], f[N][N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
char cc;
for (cin >> _; _; --_) {
cin >> n >> m;
rep (i, 1, n)
rep (j, 1, m)
if (i == 1 && j == 1) cin >> cc;
else if (i == n && j == m) cin >> cc;
else cin >> s[i][j];
rep (k, 1, n + m - 2)
rep (i, max(1, k - m + 2), min(n, 1 + k))
f[i][k - i + 2] = max(f[i - 1][k - i + 2], f[i][k - i + 1]) + s[i][k - i + 2];
cout << "Game Board #" << ++t << ": " << f[n][m] - s[n][m] << '
';
if (_ != 1) cout << '
';
}
return 0;
}
F
递归氵题
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N = 1e2 + 5;
int n, m, _, k, t;
int a[11];
char s[1030][1030];
void work(int x, int y, int c) {
if (c == 1) { s[x][y] = s[x][y + 1] = s[x + 1][y] = s[x + 1][y + 1] = 'X'; return; }
work(x, y, c - 1);
work(x + a[c - 1], y - a[c - 2], c - 1);
work(x + a[c - 1], y + a[c - 2], c - 1);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
a[0] = 1;
rep(i, 1, 10) a[i] = a[i - 1] << 1;
for (cin >> _; _; --_) {
cin >> n;
rep(i, 1, a[n]) {
rep(j, 1, a[n]) s[i][j] = ' ';
s[i][a[n] + 1] = '
';
}
work(1, a[n - 1], n);
cout << "Triangle #" << ++t << ":
";
rep(i, 1, a[n]) cout << s[i] + 1;
if (_ != 1) cout << endl;
}
return 0;
}
G
数学题, 跪了
赛后发现本质是Floyd
H
并查集, 板子
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N = 1e5 + 5;
int n, m, _, k, t;
int f[35];
int find(int x) {
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
void unit(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
f[y] = x;
}
int main()
{
for (cin >> _; _; --_) {
cin >> n >> m;
bool flag = 0;
rep (i, 1, n) f[i] = i, f[i + n] = i + n;
rep (i, 1, m) {
int x, y; string c; cin >> x >> y >> c;
int fny = find(y + n);
int fx = find(x), fy = find(y);
if (c[0] == 'T' && fx == fny) flag = 1;
else if (c[0] == 'C' && fx == fy) flag = 1;
if (c[0] == 'T') unit(x, y), unit(x + n, y + n);
else unit(x, y + n), unit(x + n, y);
}
cout << "Case #" << ++t << ": ";
if (flag) { cout << 0 << '
'; continue; }
int tot = 0;
rep (i, 1, n) if (i == f[i]) ++tot;
cout << (1 << tot) << '
';
}
return 0;
}
I
动态规划, 搜索
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(0); cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 1e5 + 5;
int n, m, _, k, t;
int a[9];
ll f[9][105];
ll find(int c, int w) {
if (w == n) return 1;
if (w > n || c > 8) return 0;
if (f[c][w] >= 0) return f[c][w];
return f[c][w] = find(c, w + a[c]) + find(c + 1, w);
}
int main() {
IO;
for (cin >> _; _; --_) {
rep (i, 1, 8) cin >> a[i];
cin >> n;
memset(f, -1, sizeof f);
find(1, 0);
cout << "Equation #" << ++t << ": " << f[1][0] << '
';
}
return 0;
}
J
见代码
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(0); cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 55;
int v[N][N], ans[55];
bool vv[N], flag;
int n, x[N], y[N], start = 1;
int line(int i, int j) { //判断i，j在不在一条直线
if (i == j) return 0;
if ((x[i] - x[j]) && !(y[i] - y[j])) return 1;
if (!(x[i] - x[j]) && (y[i] - y[j])) return 2;
return 0;
}
bool X1(int i, int j) {//判断ij之间有没有点,平行x轴
rep (k, 1, n)
if (line(i, k) == 1 && line(j, k) == 1)
if ((x[i] - x[k]) > 0 && (x[j]-x[k]) < 0) return 0;
else if ((x[i] - x[k]) < 0 && (x[j] - x[k]) > 0) return 0;
return 1;
}
bool X2(int i, int j) {//判断ij之间有没有点，平行y轴
rep (k, 1, n)
if (line(i, k) == 2 && line(j, k) == 2)
if ((y[i] - y[k]) > 0 && (y[j] -y[k]) < 0) return 0;
else if ((y[i] - y[k]) < 0 && (y[j] - y[k]) > 0) return 0;
return 1;
}
int link(int i, int j) {//判断ij能不能直连
if (i == j) return 0;
int tmp = line(i,j);
if (!tmp) return 0;
if (tmp == 1 && X1(i, j)) return 1;
else if(tmp == 2 && X2(i, j)) return 2;
return 0;
}
void dfs(int fx, int pos, int cnt) {//fx是上一条边的方向
ans[cnt] = pos;
for (int i = 1; i <= n && flag; ++i)
if(!vv[i] && v[i][pos] && v[i][pos] != fx) {
vv[i] = 1;
dfs(v[i][pos], i, cnt + 1);
vv[i] = 0;
}
if(cnt > n && pos == start) {
flag = 0;
return;
}
}
int main() {
IO;
int ttt = 1;
while (cin >> n && n) {
start = 1;
memset(ans, 0, sizeof ans);
rep (i, 1, n) {
cin >> x[i] >> y[i];
if (y[i] < y[start]) start = i;
else if (y[i] == y[start] && x[start] > x[i]) start = i;
}
rep (i, 1, n)
rep (j, i + 1, n)
v[i][j] = v[j][i] = link(i, j);
flag=1;
memset(vv,0,sizeof vv);
dfs(0, start, 1);
cout << "Polygon #" << ttt++ << ": " << ans[1];
if (line(ans[1], ans[2]) == 1)
rep (i, 2, n) cout << ' ' << ans[i];
else per (i, n, 2) cout << ' ' << ans[i];
cout << ' ' << endl;
}
return 0;
}