A - Odd Palindrome
水。
#include <bits/stdc++.h> using namespace std; #define N 110 char s[N]; inline bool work()
{
int len = strlen(s);
for (int i = ; i < len; ++i)
{
if (s[i] == s[i - ]) return false;
}
return true;
} int main()
{
while (scanf("%s", s) != EOF)
{
puts(work() ? "Odd." : "Or not.");
}
return ;
}
B - Enlarging Enthusiasm
留坑。
C - Fear Factoring
题意：定义$F(n)$ 为 n的约数和 求 $S = \sum_{a <= n <= b} F(n)$
思路：对于1-$\sqrt(b)$内的因数可以进行枚举。对于大于$\sqrt(b)$的因数，在枚举1-sqrt(b)的因数i的时候，a-b内的(a-1)/i, b/i是一段连续的数，通过求和公式即可得到
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a,b; int main()
{
while(~scanf("%lld %lld", &a, &b))
{
if(a > b) swap(a, b);
ll tmp = sqrt(b);
ll ans = ;
for(ll i = ; i <= tmp; ++i)
{
ans += i * (b / i - (a - ) / i);
ll tmp1 = max(tmp, (a - ) / i);
ll tmp2 = max(tmp, b / i);
ans += (tmp2 - tmp1) * (tmp1 + tmp2 + ) / ;
}
printf("%lld\n", ans);
}
return ;
}
D - Rainbow Roads
题意：彩虹：一条路径当中，相邻的两条边，权值都不同 好点：以某个点为端点的所有简单路径当中，都是彩虹。 求一棵树当中有多少个好点
思路：两种情况
1° DFS下去碰到相邻的两条边，那么这两条边的最上面的那个点上面的其他所有点都不是好点，这两条边最下面那个点的子树的所有点，都不是好点
2°以某个点为根的子树中，有两个直系儿子的边权相同，那么这两个儿子的子树的所有点都不是好点
DFS序 区间标记
#include<bits/stdc++.h>
using namespace std;
#define N 50010
struct node{
int v;
int c;
inline node(){}
inline node(int v,int c) :v(v),c(c){}
inline bool operator < (const node &b) const
{
return c < b.c;
}
};
int n;
vector<node>G[N];
int fa[N];
int son[N];
int ord[N];
int dro[N];
int arr[N];
int cnt;
inline void Init()
{
cnt = ;
memset(arr, , sizeof arr);
for(int i = ; i <= n; ++i)
{
G[i].clear();
}
}
inline void DFS(int u,int pre)
{
fa[u] = pre;
ord[u] = ++cnt;
dro[cnt] = u;
son[u] = ;
for(auto it : G[u])
{
int v = it.v;
if(v == pre) continue;
DFS(v, u);
son[u] += son[v];
}
}
int main()
{
while(~scanf("%d", &n))
{
Init();
for(int i = ; i < n; ++i)
{
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
G[u].push_back(node(v, c));
G[v].push_back(node(u, c));
}
DFS(, -);
for(int i = ; i <= n; ++i)
{
sort(G[i].begin(), G[i].end());
int len = G[i].size();
int it = ;
for(int j = it; j < len; j = it)
{
++it;
while(it < len && G[i][it].c == G[i][j].c)
{
++it;
}
if(it > j + )
{
for(int k = j; k < it; ++k)
{
int v = G[i][k].v;
if(v == fa[i])
{
++arr[ord[]];
--arr[ord[i]];
++arr[ord[i] + son[i]];
}
else
{
++arr[ord[v]];
--arr[ord[v] + son[v]];
}
}
}
}
}
for(int i = ; i <= n; ++i)
{
arr[i] += arr[i - ];
}
vector<int>vec;
for(int i = ; i <= n; ++i)
{
if(arr[i] == )
{
vec.push_back(dro[i]);
}
}
int len = vec.size();
sort(vec.begin(), vec.end());
printf("%d\n", len);
for(int i = ; i < len; ++i)
{
printf("%d\n",vec[i]);
}
}
return ;
}E - Straight Shot
题意：一个机器人，给定初始速度，问从(0,0)到(0,x)。在这段路程上存在沿着y轴方向滑动的部分街道
思路：对v进行正交分解后，很容易发现vy=$\sum_{l <= i <= n } (r - l) * vi$ 从而得到了vy，在进行计算vx，从而得到时间。
#include<bits/stdc++.h> using namespace std; double x, v, vy;
double l, r, vi, tmp; int n; int main()
{
while(~scanf("%d %lf %lf", &n, &x, &v))
{
tmp = ;
for(int i = ; i <= n; ++i)
{
scanf("%lf %lf %lf", &l, &r, &vi);
tmp += (r - l) * vi;
}
vy = tmp / x;
if(fabs(vy) > v)
{
puts("Too hard");
}
else
{
double vx = sqrt(v * v - vy * vy);
double ans = x / vx;
printf("%.3f\n", ans);
}
}
return ;
}
F - Distinct Distances
留坑。
G - Security Badge
留坑。
H - Avoiding Airports
留坑。
I - Long Long Strings
题意：有两个长度为$10_10$的DNA序列，刚开始相同，有两类操作，一种是添加，一种是删除，求两个DNA序列经过一系列操作后是否相同
思路：维护两个东西，一个是新添加的坐标，一个是在原序列中删除的坐标
新添加的话，那么在它之前添加的坐标大于等于它的都要后移一位
删除的话，如果是删除的新添加的，就直接删除，要注意新添加的坐标在它后面的都要前移一位
如果是在原序列中删除，要考虑删除的坐标是原来在它之前新添加的，要后移一位，还有在它之前的删除的都要加上
#include <bits/stdc++.h>
using namespace std; #define ll long long typedef pair <ll, char> plc; vector <ll> Del[];
vector <plc> Ins[];
char s[]; ll num; char c; inline bool Dell(int vis, ll num)
{
for (int i = , len = Ins[vis].size(); i < len; ++i) if (Ins[vis][i].first == num)
{
Ins[vis].erase(Ins[vis].begin() + i);
for (auto &it : Ins[vis]) if (it.first >= num)
--it.first;
return true;
}
return false;
} inline void Delll(int vis)
{
ll tmp = num;
for (auto &it : Ins[vis])
{
if (num >= it.first)
--tmp;
else
--it.first;
}
for (auto it : Del[vis])
{
if (it <= tmp)
++tmp;
else
break;
}
num = tmp;
} inline void work(int vis)
{
Ins[vis].clear(); Del[vis].clear();
while (scanf("%s", s), s[] != 'E')
{
scanf("%lld", &num);
if (s[] == 'I')
{
scanf(" %c", &c);
for (auto &it : Ins[vis]) if (it.first >= num)
++it.first;
Ins[vis].emplace_back(num, c);
for (int len = Ins[vis].size(), i = len - ; i >= ; --i) if (Ins[vis][i].first < Ins[vis][i - ].first)
swap(Ins[vis][i], Ins[vis][i - ]);
}
else
{
if (Dell(vis, num)) continue;
Delll(vis);
Del[vis].emplace_back(num);
for (int len = Del[vis].size(), i = len - ; i >= ; --i) if (Del[vis][i] < Del[vis][i - ])
swap(Del[vis][i], Del[vis][i - ]);
}
}
} inline bool Com()
{
if (Ins[].size() != Ins[].size() || Del[].size() != Del[].size()) return false;
for (int i = , len = Ins[].size(); i < len; ++i) if (Ins[][i].first != Ins[][i].first || Ins[][i].second != Ins[][i].second)
return false;
for (int i = , len = Del[].size(); i < len; ++i) if (Del[][i] != Del[][i])
return false;
return true;
} inline void Run()
{
work(); work();
puts(Com() ? "" : "");
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run(); return ;
}
J - Grid Coloring
题意：给出一个n * m 的地图，上面有一些点已经涂色，如果已经涂了B 那么从左上角到这个点的矩形都是B 如果是R 那么从右下角的矩形都是R 有一些空点，求有多少种染色方案
思路：F[i][j][2] 表示 到第i行第j列这个点涂0（‘B’） 或者 涂1('R') 有多少种方案
如果这个点涂0 那么它左边都是已经确定的 转移的状态就是它下面那个点涂0的方案数+涂1的方案数
如果这个点涂1，那么它下面都是已经确定了，转移的状态就是它左边那个点涂0的方案数+涂1的方案数
注意本来就是0和1的情况
#include <bits/stdc++.h>
using namespace std; #define N 50
#define ll long long int n, m;
char G[N][N];
ll dp[N][N]; inline bool Full(int x, int y, int vis)
{
if (!vis)
{
for (int i = ; i <= x; ++i)
for (int j = ; j <= y; ++j)
{
if (G[i][j] == 'R')
return false;
G[i][j] = 'B';
}
}
else
{
for (int i = x; i <= n; ++i)
for (int j = y; j <= m; ++j)
{
if (G[i][j] == 'B')
return false;
G[i][j] = 'R';
}
}
return true;
} inline bool work()
{
for (int i = ; i <= n; ++i)
{
for (int j = ; j <= m; ++j)
{
if (G[i][j] == 'B')
{
if (Full(i, j, ) == false)
return false;
}
else if (G[i][j] == 'R')
{
if (Full(i, j, ) == false)
return false;
}
}
}
return true;
} inline void Run()
{
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%s", G[i] + );
if (work() == false)
{
puts("");
continue;
}
memset(dp, , sizeof dp);
for (int i = ; i <= n; ++i) dp[i][] = ;
for (int j = ; j <= m; ++j) dp[n + ][j] = ;
for (int i = n; i >= ; --i)
{
for (int j = ; j <= m; ++j)
{
if (G[i][j] == '.')
{
dp[i][j] = dp[i + ][j] + dp[i][j - ];
}
else if (G[i][j] == 'B')
dp[i][j] = dp[i + ][j];
else
dp[i][j] = dp[i][j - ];
}
}
printf("%lld\n", dp[][m]);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run(); return ;
}
K - Spinning Up Palindromes
留坑。
L - Delayed Work
水（暴力枚举人数）
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f
#define D 1000000 double k, p, x; int main()
{
while (scanf("%lf%lf%lf", &k, &p, &x) != EOF)
{
double ans = INF;
for (int i = ; i <= D; ++i)
{
double day = (k * 1.0 / i);
ans = min(ans, x * i + p * day);
}
printf("%.3f\n", ans);
}
return ;
}
M - Unsatisfying
留坑。