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;
}
