A seats
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<char> a(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
int cnt = 0;
for(int i = 1; i <= n - 2; i ++ ) {
if(a[i] == '#' && a[i + 1] == '.' && a[i + 2] == '#') cnt ++;
}
cout << cnt;
return 0;
}B Traveling Takahashi Problem
思路：模拟，写个两点之间距离公式就可以过..
代码：
#include <bits/stdc++.h>
using namespace std;
double find(double x) {
double l = 0, r = 1e9;
while(l < r - 1e-8) {
double mid = (l + r) / 2;
if(mid * mid <= x) l = mid;
else r = mid;
}
return l;
}
double calc(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main() {
int n;
cin >> n;
vector<double> x(n + 1), y(n + 1);
for(int i = 1; i <= n; i ++ ) {
cin >> x[i] >> y[i];
}
double ans = 0;
//x[0] = x[n], y[0] = y[n];
for(int i = 1; i <= n; i ++ ) {
ans += calc(x[i], y[i], x[i - 1], y[i - 1]);
}
ans += calc(x[n], y[n], 0, 0);
printf("%lf", ans);
return 0;
}C Spiral Rotation
问题：
思路：图是一个正方形，不难发现，每次操作的含义是将整个图形顺时针旋转90°，并且每操作一次，操作的范围就小一圈。因此我们可以从最外面一圈开始枚举，最外面一圈只会被旋转一次，其次一圈会被旋转2次...以此类推，我们可以轻松写出对于任意点(x, y)在旋转一圈内的坐标变化，接下来要做的就是根据旋转次数n % 4后的值确定每个点的最终位置即可
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<char>> a((n + 1), vector<char>(n + 1)), b((n + 1), vector<char>(n + 1));
for(int i = 1; i <= n; i ++ ) {
for(int j = 1; j <= n; j ++ ) {
cin >> a[i][j];
}
}
auto change = [&](int type, int x, int y) {
/*if(type == 0) b[x][y] = a[x][y];
if(type == 1) b[x][y] = a[y][n + 1 - x];
if(type == 2) b[x][y] = a[n + 1 - x][n + 1 - y];
if(type == 3) b[x][y] = a[n + 1 - x][y];*/
if(type == 0) b[x][y] = a[x][y];
if(type == 1) b[x][y] = a[n + 1 - y][x];
if(type == 2) b[x][y] = a[n + 1 - x][n + 1 - y];
if(type == 3) b[x][y] = a[y][n + 1 - x];
};
//b = a;
for(int cnt = 1; cnt <= (n + 1) / 2; cnt ++ ) {
//if(cnt == 1)
for(int i = cnt; i <= n - cnt + 1; i ++ ) {
change(cnt % 4, cnt, i);
change(cnt % 4, n - cnt + 1, i);
change(cnt % 4, i, cnt);
change(cnt % 4, i, n - cnt + 1);
}
}
for(int i = 1; i <= n; i ++ ) {
for(int j = 1; j <= n; j ++ ) {
cout << b[i][j];
}
cout << "\n";
}
return 0;
}D
思路：由于目标串长度只有3，因此此题就是个计数题， 用map来做。对于a[i], 这个点对答案的贡献就是1 ~ i - 2内所有与之相等的字符与其的坐标差之和
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
string s;
cin >> s;
n = s.length();
vector<char> a(n + 1);
for(int i = 1; i <= n; i ++ ) {
a[i] = s[i - 1];
}
map<char, ll> cnt;
map<char, ll> ma;
ll ans = 0;
for(ll i = 1; i <= n; i ++ ) {
if(cnt[a[i]] != 0) {
if(a[i] != a[i - 1]) ans += (cnt[a[i]]) * (i - 1) - ma[a[i]];
else if(a[i] == a[i - 1]) {
ans += (cnt[a[i]] - 1) * (i - 1) - (ma[a[i]] - (i - 1));
}
}
cnt[a[i]] ++;
ma[a[i]] += i;
}
cout << ans;
return 0;
}E 3 team division
思路：简单dp。首先可以很容易想到一个dp:
dp[i][j][k][u]表示从前i个人中选择并且队伍1的力量为j，队伍2的力量为k，队伍3的力量为u的代价的最小值。由于i是小于100的，且因此jku的范围不超过500。这个dp数组肯定是爆内存的，可以通过滚动数组优化掉第一维，也可以优化掉最后一维，因为当我们知道了两个组的sum，第三个组的sum也就显而易见了， 现在考虑状态转移，在转移时，如果要把第i个人加入队伍x，只要判断这个人本身是否处于这个队伍中即可，如果处于这个队伍中，那么代价是0，反之代价则是1.可以用 !(a[i] == x)表示代价
代码：
#include <bits/stdc++.h>
using namespace std;
int dp[110][510][510];
int main() {
int n;
cin >> n;
int sum = 0;
vector<int> a(n + 1), b(n + 1), s(n + 1);
for(int i = 1; i <= n; i ++ ) {
cin >> a[i] >> b[i];
sum += b[i];
s[i] = s[i - 1] + a[i];
}
if(sum % 3) {
cout << -1;
return 0;
}
memset(dp, 0x3f, sizeof dp);
dp[0][0][0] = 0;
for(int i = 1; i <= n; i ++ ) {
for(int j = 0; j <= 500; j ++ ) {
for(int k = 0; k <= 500; k ++ ) {
if(j - b[i] >= 0) dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - b[i]][k] + !(a[i] == 1));
if(k - b[i] >= 0) dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - b[i]] + !(a[i] == 2));
if(s[i] - j - k <= 500) dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] + !(a[i] == 3));
}
}
}
if(dp[n][sum / 3][sum / 3] == 0x3f3f3f3f) cout << -1;
else cout << dp[n][sum / 3][sum / 3];
return 0;
}F
首先多个询问，且n很小，确定求最短路算法floyd
并且删边不是很好操作，那么就倒着来，把删边改成加边。加边可以在o（n2）的时间复杂度内完成对floyd的更新
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int main() {
ll n, m, q;
cin >> n >> m >> q;
vector<pair<ll, ll>> way(m + 1);
vector<ll> len(m + 1);
for(ll i = 1; i <= m; i ++ ) {
ll a, b, c;
cin >> a >> b >> c;
way[i] = {a, b};
len[i] = c;
}
map<ll, ll> ma;
vector<vector<ll>> stk(q + 1);
for(ll i = 1; i <= q; i ++ ) {
ll op;
cin >> op;
if(op == 1) {
ll id;
cin >> id;
stk[i].push_back(op);
stk[i].push_back(id);
ma[id] ++;
} else {
ll x, y;
cin >> x >> y;
stk[i].push_back(op);
stk[i].push_back(x);
stk[i].push_back(y);
}
}
vector<vector<ll>> f((n + 1), vector<ll>(n + 1, inf));
for(ll i = 1; i <= n; i ++ ) f[i][i] = 0;
for(ll i = 1; i <= m; i ++ ) {
if(!ma[i]) {
//cout << i << " " << "";
ll a = way[i].first, b = way[i].second;
f[a][b] = len[i];
f[b][a] = len[i];
}
}
for(ll k = 1; k <= n; k ++ ) {
for(ll i = 1; i <= n; i ++ ) {
for(ll j = 1; j <= n; j ++ ) {
f[i][j] = min(f[i][j], f[i][k] + f[j][k]);
}
}
}
//cout << f[1][3] << " " << "\n";
stack<ll> ans;
for(ll i = q; i >= 1; i -- ) {
auto t = stk[i];
if(t[0] == 1) {
ll a = way[t[1]].first;
ll b = way[t[1]].second;
//if(i == q - 1) cout << a << " " << b << endl;
f[a][b] = min(f[a][b], len[t[1]]);
f[b][a] = min(f[b][a], len[t[1]]);
// cout << f[2][3] << " ";
for(ll i = 1; i <= n; i ++ ) {
for(ll j = 1; j <= n; j ++ ) {
f[i][j] = min(f[i][j], f[i][a] + f[b][j] + f[a][b]);
f[i][j] = min(f[i][j], f[i][b] + f[a][j] + f[a][b]);
f[j][i] = f[i][j];
}
}
} else {
//if(i == q) cout << f[t[1]][t[2]] << " ";
if(f[t[1]][t[2]] == inf) ans.push(-1);
else ans.push(f[t[1]][t[2]]);
}
}
while(ans.size()) {
cout << ans.top() << "\n";
ans.pop();
}
return 0;
}
