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
F
首先多个询问，且n很小，确定求最短路算法floyd
并且删边不是很好操作，那么就倒着来，把删边改成加边。加边可以在o（n2）的时间复杂度内完成对floyd的更新
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n, m, q;
cin >> n >> m >> q;
vector<vector<ll>> dp((n + 1), vector<ll>(n + 1, 0x3f3f3f3f));
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;
dp[b][a] = c;
dp[a][b] = c;
way[i] = {min(a, b), max(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, 0x3f3f3f3f));
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]] == 0x3f3f3f3f) ans.push(-1);
else ans.push(f[t[1]][t[2]]);
}
}
while(ans.size()) {
cout << ans.top() << "\n";
ans.pop();
}
return 0;
}