A - Arithmetic Progression (atcoder.jp)
1.思路:循环输出即可
2.代码:
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
void solve()
{
int a,b,c;
cin >> a >> b >> c;
while (a <= b) {
cout << a << ' ';
a += c;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
while(T --) solve();
return 0;
}
B - Append (atcoder.jp)
1.思路:vector模拟即可。
2.代码:
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
void solve()
{
vector<int> v;
int q;
cin >> q;
while (q --) {
int op,x;
cin >> op >> x;
if (op == 1) {
v.pb(x);
}
else {
cout << v[v.size() - x] << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
while(T --) solve();
return 0;
}
C - Divide and Divide (atcoder.jp)
1.思路:记忆化搜索,模拟即可。
2.代码:
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
map<ll,ll> mem;
ll dfs(ll x)
{
if (x == 1) {
return 1ll;
}
if (mem.count(x)) {
return mem[x];
}
return mem[x] = (dfs(x / 2) + dfs((x + 1) / 2)) + x;
}
void solve()
{
ll n;
cin >> n;
cout << dfs(n / 2) + dfs((n + 1) / 2) << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
while(T --) solve();
return 0;
}
D - Super Takahashi Bros. (atcoder.jp)
1.思路:发现每行给出的实际上可以等价于两条边
一条是i-->i + 1 花费a
一条是i-->c 花费b
2.代码:
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
//从0开始
template<typename T>
class Graph {
using pli = pair<T,int>;
private:
const int n;
vector<vector<pair<int,int>>> g;
public:
Graph(int _n): n(_n) {
g.resize(n);
}
void addEdge(int x,int y,int z = 0) {
g[x].push_back({y,z});
}
vector<T> shortestPath(int s) {
vector<T> dis(n);
memset(dis.data(),0x3f,dis.size() * sizeof(T));
priority_queue<pli,vector<pli>,greater<pli>> q;
q.push({0,s});
dis[s] = 0;
while(!q.empty()) {
auto [val,ver] = q.top();
q.pop();
if(val != dis[ver]) {
continue;
}
for(auto &[y,w]: g[ver]) {
if(dis[y] > val + w) {
dis[y] = val + w;
q.push({dis[y],y});
}
}
}
return dis;
}
};
void solve()
{
int n;
cin >> n;
Graph<ll> g(n);
for (int i = 1;i < n;i ++) {
int a,b,c;
cin >> a >> b >> c;
g.addEdge(i - 1,i,a);
g.addEdge(i - 1,c - 1,b);
}
auto p = g.shortestPath(0);
cout << p[n - 1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
while(T --) solve();
return 0;
}
E - Mancala 2 (atcoder.jp)
1.思路:按照模拟的过程可以分为三段去操作,从当前位置到末尾+轮多少圈+剩下的次数。
发现这是一个需要维护区间加和单点查询的数据结构题目,因此我们考虑直接用树状数组维护原数组差分即可。或者直接用线段树维护原数组也行。
2.代码:
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
template <typename T>
struct Fenwick {
const int n;
std::vector<T> a;
Fenwick (int n) : n(n), a(n + 1) {}
void add(int pos, T x) {
for (int i = pos; i <= n; i += i & -i) {
a[i] += x;
}
}
T query(int x) {
T res = 0;
for (int i = x; i; i -= i & -i) {
res += a[i];
}
return res;
}
T query(int l, int r) {
if (l == 0 || l > r) {
return 0;
}
return query(r) - query(l - 1);
}
//找到大于k得第一个地方
T kth(int k) {
int pos = 0;
for(int j = 31 - __builtin_clz(n);j >= 0;j --) {
if(pos + (1 << j) <= n && k > a[pos + (1 << j)]) {
pos += 1 << j;
k -= a[pos];
}
}
return pos + 1;
}
};
void solve()
{
int n,q;
cin >> n >> q;
Fenwick<ll> fen(n);
int pre = 0,x;
for (int i = 1;i <= n;i ++) {
cin >> x;
fen.add(i,x - pre);
pre = x;
}
for (int i = 1;i <= q;i ++) {
cin >> x;
x ++;
ll rs = fen.query(x);
ll mi = min(rs,0ll + n - x);
fen.add(x,-rs);
fen.add(x + 1,rs);
if (mi) {
rs -= mi;
fen.add(x + 1,1);
fen.add(x + 1 + mi,-1);
}
if (rs) {
ll cz = rs / n,cm = rs % n;
fen.add(1,cz);
fen.add(1,1);
fen.add(1 + cm,-1);
}
}
for (int i = 1;i <= n;i ++) {
cout << fen.query(i) << ' ';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
while(T --) solve();
return 0;
}
F - S = 1 (atcoder.jp)
1.思路:考虑使用鞋带公式化简,我们可以得到,这么个方程|ay - bx| = 2,考虑把绝对值拆开,做两次exgcd求解即可。
2.代码:
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve()
{
ll a,b;
cin >> a >> b;
ll x,y;
ll d1 = exgcd(a,-b,y,x);
if (2 % d1) {
ll d2 = exgcd(b,-a,x,y);
x *= 2 / d2,y *= 2 / d2;
if (2 % d2) {
cout << -1 << endl;
}
else {
cout << x << ' ' << y << '\n';
}
}
else {
x *= 2 / d1,y *= 2 / d1;
cout << x << ' ' << y << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
while(T --) solve();
return 0;
}
G - Leaf Color (atcoder.jp)
1.思路:考虑每个遍历每个颜色单独求一遍答案,因此可以建一棵虚树进行dp即可。
f[i] 表示以i为根节点,(不管符不符合的答案为多少),g[i]表示。
当i为枚举的颜色时,答案加上f[i]的方案数即可。
当i不是枚举的颜色时,首先f[i]应该-1(因为i不能作为根节点),其次答案应该加上f[i] - g[i](所有选择一个子树的方案和)。
2.代码:
#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
using i64 = long long;
constexpr int P = 998244353;
// assume -P <= x < 2P
int Vnorm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Mint {
int x;
Mint(int x = 0) : x(Vnorm(x)) {}
Mint(i64 x) : x(Vnorm(x % P)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(Vnorm(P - x));
}
Mint inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Mint &operator*=(const Mint &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = Vnorm(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = Vnorm(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, Mint &a) {
i64 v;
is >> v;
a = Mint(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Mint &a) {
return os << a.val();
}
};
vector<int> son[N],g[N];
int c[N],dep[N],dfn[N],fa[N][20],stk[N],top,tim;
inline void dfs(int u,int f)
{
dfn[u] = ++ tim;
dep[u] = dep[f] + 1;
fa[u][0] = f;
for(int i = 1;i <= 18;i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(auto v : g[u]) {
if(v == f) continue;
dfs(v,u);
}
}
inline int LCA(int x,int y)
{
if(dep[x] > dep[y]) swap(x,y);
int d = dep[y] - dep[x];
for(int i = 18;i >= 0;i --) {
if(d >> i & 1) y = fa[y][i];
}
if(x == y) return x;
for(int i = 18;i >= 0;i --) {
if(fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
Mint ans = 0;
int tarc = 0;
void add(int &a,int &b)
{
son[a].push_back(b);
}
Mint DP(int x)
{
Mint f = 1,g = 0;
for (auto &y: son[x]) {
auto nf = DP(y);
f *= (nf + 1);
g += nf;
}
if (c[x] == tarc) {
ans += f;
}
else {
f -= 1;
ans += f - g;
}
son[x].clear();
return f;
}
void buildTree(vector<int> &ver)
{
if (ver.size() == 1) {
ans += 1;
return;
}
sort(ver.begin(),ver.end(),[&](int &x,int &y){
return dfn[x] < dfn[y];
});
stk[top = 1] = 1;
if (ver[0] != 1) {
stk[++ top] = ver[0];
}
for (int i = 1;i < ver.size();i ++) {
int lca = LCA(ver[i],stk[top]);
while (top > 1 && dfn[stk[top - 1]] >= dfn[lca]) {
add(stk[top - 1],stk[top]);
top --;
}
if (lca != stk[top]) {
add(lca,stk[top]);
stk[top] = lca;
}
stk[++ top] = ver[i];
}
while (top) {
add(stk[top - 1],stk[top]);
top --;
}
DP(1);
}
vector<int> cor[N];
void solve()
{
int n;
cin >> n;
for (int i = 1;i <= n;i ++) {
cin >> c[i];
cor[c[i]].push_back(i);
}
for (int i = 1;i < n;i ++) {
int a,b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,0);
for (int i = 1;i <= n;i ++) {
if (cor[i].size()) {
tarc = i;
buildTree(cor[i]);
}
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
while(T --) solve();
return 0;
}