A：
思路：直接取出每一位暴力就可以了
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int a[1000005];
int main(){
int n; scanf("%d", &n);
int tot=0;
while(n){
a[++tot]=n%10;
n/=10;
}
int ans=0;
for(int i=1; i<=tot; i++){
ans=ans*10+a[i]+a[tot-i+1];
}
cout<<ans<<endl;
return 0;
}
B:
思路：类似01背包
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL a[100005], f[2][3650];
int main(){
int t; scanf("%d", &t);
while(t--){
int n; scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld", &a[i]);
}
memset(f, 0, sizeof(f));
int I=1, F=0;
f[1][a[1]%3600]=1;
if(f[1][0]==1){
printf("YES\n");
continue;
}
for(int i=2; i<=n; i++){
I^=1;
for(int i=0; i<=3600; i++) f[I][i]=0;
f[I][a[i]%3600]=1;
for(int s=0; s<3600; s++){
if(f[I^1][s]) f[I][(s+a[i])%3600]=1;
f[I][s]=max(f[I^1][s], f[I][s]);
if(f[I][0]==1){
F=1;
break;
}
}
if(F) break;
}
if(F){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
C：
思路：打表+二分
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL s[5000000];
int main(){
int tot=0;
for(LL i=0; i*i<=1000000000; i++){
s[++tot]=i*i;
}
int n; scanf("%d", &n);
for(int i=1; i<=n; i++){
LL l, r; scanf("%lld%lld", &l, &r);
LL pos2=upper_bound(s+1, s+tot+1, r)-s;
LL pos1=lower_bound(s+1, s+tot+1, l)-s;
printf("%lld\n", pos2-pos1);
}
return 0;
}
D：
思路一：题解的思路
思路二：BFS序
思路一：
//#pragma GCC optimize(3)
#include <random>
#include <stdio.h>
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
#define fst first
#define sed second
#define psb push_back
#define Break(x) { x; break; }
#define Return(x) { x; return; }
#define Continue(x) { x; continue; }
#define lowbit(x) ((x) & -(x))
#define sqr(x) (1LL * (x) * (x))
#define sign(x) (((x) > 0) - ((x) < 0))
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define MEM(x, y) memset((x), (y), sizeof(x))
#define MEN(x, y, z) memset((x), (y), sizeof((x)[0]) * (z))
#define Diz(x) (lower_bound(dz.begin(), dz.end(), (x)) - dz.begin())
#define DISCRETE(x) (x).push_back(INT_MIN), (sizeof((x).back()) == 8 ? (x).back() = LLONG_MIN : 0), sort((x).begin(), (x).end()), (x).erase(unique((x).begin(), (x).end()), (x).end())
#ifdef LOCAL
#define DEBUG(...) cout << ">> " << #__VA_ARGS__ << " =", PRT(__VA_ARGS__), cout << endl;
#define DEBUGS(...) cout << ">> " << #__VA_ARGS__ << " =", PRTS(__VA_ARGS__), cout << endl;
#define DEBUGA(...) cout << ">> " << #__VA_ARGS__ << " =", PRTA(__VA_ARGS__), cout << endl;
void PRT() {} template <typename S, typename... T> void PRT(S x, T ... y){ cout << " " << x; PRT(y...); }
void PRTS() {} template <typename S> void PRTS(S x) { for (auto v : x) cout << " " << v; }
void PRTA() {} template <typename S, typename T> void PRTA(S x, T y) { while (y--) cout << " " << *x, ++x; }
#define TIME cout << "Runing time: " << clock() << "ms\n", 0
#define __int128_t long long
#define __gcd(x, y) _Gcd((x), (y))
#define __builtin_popcount(x) _BitCnt((uint)(x))
#define __builtin_popcountll(x) _BitCnt((ull)(x))
#else
#define DEBUG(...) ;
#define DEBUGS(...) ;
#define DEBUGA(...) ;
#define TIME 0
#endif
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int dir[8][2] = { -1, 0, 1, 0, 0, -1, 0, 1, -1, -1, -1, 1, 1, -1, 1, 1 };
template<typename S, typename T> inline bool Min(S &a, const T &b){ return a > b ? a = b, true : false; }
template<typename S, typename T> inline bool Max(S &a, const T &b){ return a < b ? a = b, true : false; }
template<typename S, typename T> inline void Adm(S &a, const T &b){ a = (a + b) % MOD; if (a < 0) a += MOD; }
template<typename T> inline bool IsPri(T x) { if (x < 2) return false; for (T i = 2; i * i <= x; ++i) if (x % i == 0) return false; return true; }
template<typename T> inline T _Gcd(T a, T b){ while (b){ T t = b; b = a % b; a = t; } return a; }
template<typename T> inline int _BitCnt(T x){ int cnt = 0; while (x)++cnt, x &= x - 1; return cnt; }
inline ll Pow(ll a, ll n) { ll t = 1; a %= MOD; while (n > 0) { if (n & 1) t = t * a % MOD; a = a * a % MOD, n >>= 1; } return t % MOD; }
#define gc p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
inline int read(){ static char buf[1000000], *p1 = buf, *p2 = buf; register int x = false; register char ch = gc; register bool sgn = false; while (ch != '-' && (ch < '0' || ch > '9')) ch = gc; if (ch == '-') sgn = true, ch = gc; while (ch >= '0'&& ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc; return sgn ? -x : x; }
//能ll就开 函数内判非法 已知大小vector初始化 ""[] vector* nm全局函数默认传参 需要多开和嵌套再开结构体
const int N = 8e5;
vector<int> e[N];
int fz[N], a0[N], a1[N], a2[N]; //向上跳012次的标记
void DFS(int x, int f)
{
fz[x] = f;
for (int y : e[x])
if (y != f)
DFS(y, x);
}
int main()
{
#ifdef LOCAL
freopen("C:/input.txt", "r", stdin);
//freopen("C:/output.txt", "w", stdout);
#endif
int n, q;
cin >> n >> q;
for (int i = 1; i < n; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
DFS(1, 0);
while (q--)
{
int x;
scanf("%d", &x);
++a0[x];
if (fz[x])
++a1[fz[x]];
if (fz[fz[x]])
++a2[fz[fz[x]]];
int res = a0[fz[fz[x]]] + a0[fz[x]] + a1[fz[x]] + a1[x] + a2[x];
if (x == 1)
res = a0[x] + a1[x] + a2[x];
printf("%d\n", res);
}
return TIME;
}
思路二：
//#pragma GCC optimize(3)
#include <random>
#include <stdio.h>
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
#define fst first
#define sed second
#define psb push_back
#define Break(x) { x; break; }
#define Return(x) { x; return; }
#define Continue(x) { x; continue; }
#define lowbit(x) ((x) & -(x))
#define sqr(x) (1LL * (x) * (x))
#define sign(x) (((x) > 0) - ((x) < 0))
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define MEM(x, y) memset((x), (y), sizeof(x))
#define MEN(x, y, z) memset((x), (y), sizeof((x)[0]) * (z))
#define Diz(x) (lower_bound(dz.begin(), dz.end(), (x)) - dz.begin())
#define DISCRETE(x) (x).push_back(INT_MIN), (sizeof((x).back()) == 8 ? (x).back() = LLONG_MIN : 0), sort((x).begin(), (x).end()), (x).erase(unique((x).begin(), (x).end()), (x).end())
#ifdef LOCAL
#define DEBUG(...) cout << ">> " << #__VA_ARGS__ << " =", PRT(__VA_ARGS__), cout << endl;
#define DEBUGS(...) cout << ">> " << #__VA_ARGS__ << " =", PRTS(__VA_ARGS__), cout << endl;
#define DEBUGA(...) cout << ">> " << #__VA_ARGS__ << " =", PRTA(__VA_ARGS__), cout << endl;
void PRT() {} template <typename S, typename... T> void PRT(S x, T ... y){ cout << " " << x; PRT(y...); }
void PRTS() {} template <typename S> void PRTS(S x) { for (auto v : x) cout << " " << v; }
void PRTA() {} template <typename S, typename T> void PRTA(S x, T y) { while (y--) cout << " " << *x, ++x; }
#define TIME cout << "Runing time: " << clock() << "ms\n", 0
#define __int128_t long long
#define __gcd(x, y) _Gcd((x), (y))
#define __builtin_popcount(x) _BitCnt((uint)(x))
#define __builtin_popcountll(x) _BitCnt((ull)(x))
#else
#define DEBUG(...) ;
#define DEBUGS(...) ;
#define DEBUGA(...) ;
#define TIME 0
#endif
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int dir[8][2] = { -1, 0, 1, 0, 0, -1, 0, 1, -1, -1, -1, 1, 1, -1, 1, 1 };
template<typename S, typename T> inline bool Min(S &a, const T &b){ return a > b ? a = b, true : false; }
template<typename S, typename T> inline bool Max(S &a, const T &b){ return a < b ? a = b, true : false; }
template<typename S, typename T> inline void Adm(S &a, const T &b){ a = (a + b) % MOD; if (a < 0) a += MOD; }
template<typename T> inline bool IsPri(T x) { if (x < 2) return false; for (T i = 2; i * i <= x; ++i) if (x % i == 0) return false; return true; }
template<typename T> inline T _Gcd(T a, T b){ while (b){ T t = b; b = a % b; a = t; } return a; }
template<typename T> inline int _BitCnt(T x){ int cnt = 0; while (x)++cnt, x &= x - 1; return cnt; }
inline ll Pow(ll a, ll n) { ll t = 1; a %= MOD; while (n > 0) { if (n & 1) t = t * a % MOD; a = a * a % MOD, n >>= 1; } return t % MOD; }
#define gc p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
inline int read(){ static char buf[1000000], *p1 = buf, *p2 = buf; register int x = false; register char ch = gc; register bool sgn = false; while (ch != '-' && (ch < '0' || ch > '9')) ch = gc; if (ch == '-') sgn = true, ch = gc; while (ch >= '0'&& ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc; return sgn ? -x : x; }
//能ll就开 函数内判非法 已知大小vector初始化 ""[] vector* nm全局函数默认传参 需要多开和嵌套再开结构体
const int N = 8e5;
vector<int> e[N];
int fz[N], son[N]; //父节点 是否有儿子
int id[N], l[N], r[N], idx; //当前编号 儿子编号范围
void DFS(int x, int f)
{
fz[x] = f, son[x] = SZ(e[x]) - !!fz[x];
if (son[x])
l[x] = idx + 1;
for (int y : e[x])
if (y != f)
id[y] = ++idx;
if (son[x])
r[x] = idx;
for (int y : e[x])
if (y != f)
DFS(y, x);
}
ll a[N], c1[N], c2[N];
void _Add(int x, ll v)
{
for (int i = x; i < N; i += lowbit(i))
c1[i] += v, c2[i] += v * x;
}
void Add(int l, int r, ll v)
{
_Add(l, v), _Add(r + 1, -v);
}
ll _Ask(int x)
{
ll res = 0;
for (int i = x; i; i -= lowbit(i))
res += c1[i] * (x + 1) - c2[i];
return res;
}
ll Ask(int l, int r)
{
return _Ask(r) - _Ask(l - 1);
}
int main()
{
#ifdef LOCAL
freopen("C:/input.txt", "r", stdin);
//freopen("C:/output.txt", "w", stdout);
#endif
int n, q;
cin >> n >> q;
for (int i = 1; i < n; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
id[1] = ++idx, DFS(1, 0);
// for(int i=1; i<=n; i++){
// cout<<i<<" son["<<i<<"]="<<son[i]<<" l: "<<l[i]<<" r: "<<r[i]<<endl;
// }
while (q--)
{
int x;
scanf("%d", &x);
ll res = Ask(id[x], id[x]) + a[x] + 1;
if (fz[x])
{
res += Ask(id[fz[x]], id[fz[x]]);
Add(id[fz[x]], id[fz[x]], 1);
}
if (son[x])
{
res += Ask(l[x], r[x]) ;
Add(l[x], r[x], 1);
}
a[x] -= SZ(e[x]) - 1;
printf("%lld\n", res);
}
return TIME;
}E：
思路：f[i]：1 1 2 3 5......我们把表打出来。然后后面两种网上都有实现方法。这题就写完了。
京公网安备 11010502036488号