①P2831 愤怒的小鸟
涉及到计算几何的（其实是数学）的搜索，做法可以搜索或者状压，但我都不会QAQ
搜索时首先考虑是否能与之前生成的二次曲线相交，若可以则直接往下搜
否则考虑与之前的孤立点建立曲线，删除孤立点后继续搜索（记得回溯）
最后在将该点加入孤立点，供后续的点用于构造曲线，然后再搜索
#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-6;
const int maxn = 1e6 + 10;
const int inf = 1e9;
int n, m;
struct Point {
double x, y;
}p[20];
inline int dcmp(double x)//cmp x with 0
{
if (fabs(x) <= eps)return 0;
return x < 0 ? -1 : 1;
}
inline int cmp(double x, double y)
{
//x>y return 1
//x<y reutrn -1
//x==y return 0
return dcmp(x - y);
}
double lina[20], linb[20], apx[20], apy[20];
int ans;
bool check(int p, double x, double y)
{
if (cmp(lina[p] * pow(x, 2) + linb[p] * x, y) == 0)
return 1;
return 0;
}
void dele(int p,int LIM)
{
for (int i = p; i <= LIM; i++)
apx[i] = apx[i + 1], apy[i] = apy[i + 1];
}
void repla(int p, int LIM, double x,double y)
{
for (int i = LIM; i > p; i--)
apx[i] = apx[i - 1], apy[i] = apy[i - 1];
apx[p] = x, apy[p] = y;
}
void dfs(int now, int lincnt, int acnt)
{
if (lincnt + acnt >= ans)return;
if (now > n)
{
ans = lincnt + acnt;
return;
}
//a line cross the point
for (int i = 1; i <= lincnt; i++)
{
if (check(i, p[now].x, p[now].y))
{
dfs(now + 1, lincnt, acnt);
return;
}
}
//creat a line
for (int i = 1; i <= acnt; i++)
{
if (cmp(p[now].x, apx[i]) == 0)continue;//这样解出的不是抛物线
double a = (p[now].y * apx[i] - apy[i] * p[now].x) / (p[now].x * p[now].x * apx[i] - apx[i] * apx[i] * p[now].x);
if (cmp(a, 0) != -1)continue;//必须是抛物线
double b = (p[now].y - p[now].x * p[now].x * a) / p[now].x;
//cout << a << " " << b << endl;
double tmpx = apx[i], tmpy = apy[i];//记录回溯的值
lina[lincnt + 1] = a;
linb[lincnt + 1] = b;
dele(i, acnt);//删除点
dfs(now + 1, lincnt + 1, acnt - 1);
repla(i, acnt, tmpx, tmpy);//回溯这个点
}
//以上情况都已尝试，最后尝试将该点孤立去与后面的点构造曲线
apx[acnt + 1] = p[now].x;
apy[acnt + 1] = p[now].y;
dfs(now + 1, lincnt, acnt + 1);
}
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
ans = n;
for (int i = 1; i <= n; i++)
{
double x, y;
cin >> x >> y;
p[i] = { x,y };
}
dfs(1, 0, 0);
cout << ans << endl;
}
return 0;
}
②acwing 2069. 网络分析
用并查集维护构造树进行树上差分
#include<bits/stdc++.h>
#include<unordered_map>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-6;
const int maxn = 1e5 + 10;
const int inf = 1e9;
ll mod = 998244353;
int edge_cnt = 0, head[maxn];
struct edge {
int to;
int next;
}e[maxn << 1];
inline void add(int from, int to)
{
e[++edge_cnt] = { to,head[from] };
head[from] = edge_cnt;
}
int fa[maxn];
int anc(int x)
{
return fa[x] == x ? x : fa[x] = anc(fa[x]);
}
int ans[maxn];
int n, m;
void dfs(int from)
{
for (int i = head[from]; i != -1; i = e[i].next)
{
int to = e[i].to;
ans[to] += ans[from];
dfs(to);
}
}
int main()
{
//fastio;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= 2 * n; i++)
fa[i] = i;
int cnt = n + 1;
while (m--)
{
int o, x, y;
scanf("%d%d%d", &o, &x, &y);
if (o == 1)
{
x = anc(x), y = anc(y);
if (x != y)
{
fa[x] = fa[y] = cnt;
add(cnt, x);
add(cnt, y);
cnt++;
}
}
else
{
ans[anc(x)] += y;
}
}
for (int i = n + 1; i < cnt; i++)
{
//cout << i << " " << fa[i] << endl;
if (fa[i] == i)
dfs(i);
}
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}
③acwing 2068. 整数拼接
开一个二位dp数组，假设这个数为x，在第二维的x%k这一个位置的第一维上记录x末尾加上i位再模k的值，之后就直接查询之前是否出现过一个数模k能和现在这个数模k相加等于k的倍数即可
#include<bits/stdc++.h>
#include<unordered_map>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-6;
const int maxn = 1e5 + 10;
const int inf = 1e9;
ll mod;
ll dp[20][maxn], a[maxn];
ll ans, n;
ll mi(ll x)
{
ll res = 0;
while (x)
{
x /= 10;
res++;
}
//cout << res << endl;
return res;
}
void solve()
{
for (int i = 1; i <= n; i++)
{
ans += dp[mi(a[i])][(mod - a[i] % mod) % mod];
//cout << mi(a[i]) << " " << mod - a[i] % mod <<" "<< dp[mi(a[i])][mod - a[i] % mod] << endl;
ll tmp = a[i] % mod;
for (int j = 1; j <= 10; j++)
{
tmp = tmp * 10 % mod;
dp[j][tmp]++;
}
}
}
int main()
{
fastio;
cin >> n >> mod;
for (int i = 1; i <= n; i++)
cin >> a[i];
ans = 0;
solve();
reverse(a + 1, a + n + 1);
memset(dp, 0, sizeof(dp));
solve();
cout << ans;
return 0;
}