A.想要更多的0---数学 + 二分
快速求 1-n中 0 的个数 可参照 求 1 的个数
<编程之美>计算0到N中包含数字1的个数 - VIPWTL - 博客园 (cnblogs.com)
#include<iostream>
using namespace std;
#define int long long
int cal_0(int n)
{
int sum = 1;
int fac = 1, low = 0, cur = 0, high = 0;
// 当前因子 低位 现在处理的位 高位
while(n / fac)
{
low = n - (n / fac) * fac;
cur = (n / fac) % 10;
high = n / (fac * 10);
if(cur == 0) sum += (high - 1) * fac + low + 1;
else sum += high * fac;
fac *= 10;
}
return sum;
}
signed main()
{
int n, k;
cin >> n >> k;
int l = 0, r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(cal_0(n) - cal_0(mid - 1) >= k) l = mid;
else r = mid - 1;
}
if(cal_0(n) < k) r = -1;
cout << r << '\n';
}
B --- 初中数学
萌新的蒟蒻解法
#include<iostream>
using namespace std;
signed main()
{
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
double k = 1.0 * (y2 - y1) / (x2 - x1);
double x = 1.0 * (x2 * y2 + x1 * y1) / (k * (x1 + x2) + y1 + y2);
printf("%.6lf %.6lf\n",x,k * x);
}
C --- 小模拟
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
char g[4][50]=
{
{' '},
{' ','q','w','e','r','t','y','u','i','o','p'},
{' ','a','s','d','f','g','h','j','k','l'},
{' ',' ','z','x','c','v','b','n','m'},
};
map<char,pair<int,int> > mp;
signed main()
{
int T; cin >> T;
for(int i = 1; i <= 3; i ++)
for(int j = 1; j <= 11-i; j ++)
mp[g[i][j]] = {i, j};
while(T --)
{
string s; cin >> s;
for(auto c : s)
{
if(isupper(c))
{
c = tolower(c);
cout<<"3 1 " ;
}
cout << mp[c].first <<" "<<mp[c].second<<'\n';
}
}
}
D --- dfs 序 + 性质
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n, q;
vector<int> g[N];
int din[N], dout[N];
int timestamp = 0;
void dfs(int u)
{
din[u] = ++ timestamp;
for(auto v : g[u])
dfs(v);
dout[u] = ++ timestamp;
}
signed main()
{
cin >> n >> q;
for(int i = 2; i <= n; i ++)
{
int u; cin >> u;
g[u].push_back(i);
}
// 预处理出 dfs 序
dfs(1);
while(q --)
{
int a, b, x; cin >> a >> b;
int maxv = 0, minv = 1e9;
while(a --)
{
cin >> x;
minv = min(minv, din[x]);
maxv = max(maxv, dout[x]);
}
bool flag = false;
while(b --)
{
cin >> x;
if(din[x] < minv && dout[x] > maxv)
flag = true;
}
if(flag) cout << "yes" << '\n';
else cout << "no" << '\n';
}
}
E 状态机dp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 200010;
double f[N][2][2];
// f[i][j][k] 前 i 个物品中
// j k分别表示2人是否施加魔法
double cal(int x1, int y1, int x2, int y2)
{
double t = 1.0 * (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
return sqrt(t);
}
signed main()
{
int ax, ay, bx, by, cx, cy;
cin >> ax >> ay >> bx >> by >> cx >> cy;
int n; cin >> n;
memset(f, 0x7f, sizeof f);
f[0][0][0] = 0;
for(int i = 1; i <= n; i ++)
{
int x, y; cin >> x >> y;
double dis0 = cal(ax, ay, x, y) + cal(cx, cy, x, y);
double dis1 = cal(bx, by, x, y) + cal(cx, cy, x, y);
double dis = 2 * cal(cx, cy, x, y);
f[i][1][0] = min(f[i - 1][0][0] + dis0, f[i - 1][1][0] + dis);
f[i][0][1] = min(f[i - 1][0][0] + dis1, f[i - 1][0][1] + dis);
f[i][1][1] = min({f[i - 1][0][1] + dis0, f[i - 1][1][0] + dis1, f[i - 1][1][1] + dis});
}
double res = min({f[n][0][1], f[n][1][0], f[n][1][1]});
printf("%.2lf\n",res);
}
F --- Nim 游戏 + 暴力
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
signed main()
{
cin >> n;
int sum = 0;
for(int i = 1; i <= n; i ++) cin >> a[i], sum ^= a[i];
for(int i = 0; i < a[1]; i ++)
{
for(int j = 1; j <= n; j ++)
{
int a1 = a[1] - i;
int a2 = a[j] + i;
int t = sum ^ a[1] ^ a[j] ^ a1 ^ a2;
if(t == 0)
{
cout << i << '\n';
return 0;
}
}
}
cout << -1 << '\n';
}
G
解法一：树状数组 + 二分 + 循环链表 + 巨多细节
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 500010, mod = 1e9 + 7;
int n, k, p;
int tr[N]; //树状数组
int cnt; // 剩余场地数量
int now; // 当前所在场地编号
int head = 1; // 第一个场地编号
int res = 0;
int pre_x;
struct node
{
int pre, next;
}a[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x,int v)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void remove(int x)
{
a[a[x].pre].next = a[x].next;
a[a[x].next].pre = a[x].pre;
add(x, -1);
if(x == head) head = a[x].next;
cnt --;
}
void rotate(int i, int x, int y)
{
int rsum = query(n) - query(now);
if(x > rsum) x -= rsum + 1, now = head;
int l = now, r = n;
int lsum = query(now);
while(l < r)
{
int mid = l + r >> 1;
if(x + lsum <= query(mid)) r = mid;
else l = mid + 1;
}
now = r;
res = (res + i * (pre_x + y) * now) % mod;
if(y <= p) remove(now), now = a[now].next;
}
signed main()
{
cin >> n >> k >> p;
for(int i = 1; i <= n; i ++)
{
a[i].next = i + 1;
a[i].pre = i - 1;
}
a[1].pre = n, a[n].next = 1;
now = 1; cnt = n;
for(int i = 1; i <= n; i ++) add(i, 1);
for(int i = 1; i <= k; i ++)
{
int op, x, y;
cin >> op >> x >> y;
pre_x = x; x %= cnt;
if(op == 1) rotate(i, x, y);
else rotate(i,cnt - x, y);
}
cout << res << '\n';
}
解法二：线段树 + 模拟
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define int long long
const int N = 2000010 , mod = 1e9 + 7;
int tr[N];
int n, k, p;
void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = 1;
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1,mid + 1, r);
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
int query_id(int u, int l, int r, int x)
{
if(l == r) return r;
int mid = l + r >> 1;
if(tr[u << 1] >= x) return query_id(u << 1, l, mid, x);
else return query_id(u << 1 | 1, mid + 1, r, x - tr[u << 1]);
}
int query_sum(int u, int l, int r, int pos)
{
if(r <= pos) return tr[u];
int mid = l + r >> 1;
if(pos <= mid) return query_sum(u << 1, l, mid, pos);
else return tr[u << 1] + query_sum(u << 1 | 1, mid + 1, r, pos);
}
void sub(int u, int l, int r, int pos)
{
tr[u] --;
if(l == r) return ;
int mid = l + r >> 1;
if(pos <= mid) sub(u << 1, l, mid, pos);
else sub(u <<1 | 1, mid + 1, r, pos);
}
signed main()
{
cin >> n >> k >> p;
build(1, 1, n);
int now = 1, res = 0, sum = 0;
for(int i = 1; i <= k; i ++)
{
int op, x, y; cin >> op >> x >> y;
int pre_x = x;
x = x % tr[1];
if(op == 1)
{
sum = query_sum(1, 1, n, now); // 前面的场地数量
if(tr[1] - sum >= x) now = query_id(1, 1, n, x + sum);
else now = query_id(1, 1, n, x + sum - tr[1]);
}
else
{
if(now == 1) sum = 0;
else sum = query_sum(1, 1, n, now - 1);
if(sum >= x) now = query_id(1, 1, n, sum - x + 1);
else now = query_id(1, 1, n, sum - x + 1 + tr[1]);
}
res = (res + i * (pre_x + y) * now) % mod;
if(y <= p)
{
sum = query_sum(1, 1, n, now);
if(sum == tr[1])
{
sub(1, 1, n, now);
now = query_id(1, 1, n, 1);
}
else
{
sub(1, 1, n, now);
now = query_id(1, 1, n, sum);
}
}
}
cout << res << '\n';
}
H --- 签到
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int N = 10000010 , mod = 1e11+3;
int f[N];
signed main()
{
int n; cin >> n;
f[1] = 1, f[2] = 3;
for(int i = 3; i <= n; i ++)
f[i] = (f[i-1] + f[i-2]) % mod;
int res = 0;
for(int i = 1; i <= n; i ++)res = (res + f[i]) % mod;
cout<<res<<'\n';
}
I
防AK题 不会 。。。
J --- 字符串区间 dp
类型题变形
3280 -- Cheapest Palindrome (poj.org)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1010;
map<char,int> add, del;
int f[N][N];
signed main()
{
int n; cin >> n;
string s; cin >> s; s = " " + s;
int a, b, c, d;
cin >> a >> b >> c >> d;
del['('] = a; add['('] = b;
del[')'] = c; add[')'] = d;
for(int len = 1; len <= n; len ++)
{
for(int i = 1; i + len -1 <= n; i ++)
{
int j = i + len - 1;
if(s[i] != s[j])
{
if(len <= 2) f[i][j] = 0;
else f[i][j] = f[i + 1][j - 1];
}
else
{
// 如果 s[i] = s[j] 可以删除它自己 ， 否则 加上 相反的括号
char rev = s[i] == '(' ? ')' : '(';
int x = min(f[i + 1][j] + add[rev], f[i][j - 1] + add[rev]);
int y = min(f[i + 1][j] + del[s[i]], f[i][j - 1] + del[s[j]]);
f[i][j] = min(x, y);
}
}
}
cout << f[1][n] << '\n';
}
K --- 数学公式
#include <iostream>
#include <vector>
using namespace std;
#define int long long
bool is_prime(int x)
{
if(x < 2) return false;
for(int i = 2; i <= x / i; i ++)
if(x % i == 0)return false;
return true;
}
signed main()
{
vector<int> pri;
for(int i = 1; i <= 1000; i ++)
if(is_prime(i)) pri.push_back(i * i * i * i);
int T; cin >> T;
while(T --)
{
int minv, maxv; cin >> minv >> maxv;
int l = 0, r = pri.size() - 1;
while(pri[l] < minv) l ++;
while(pri[r] > maxv) r --;
cout << r - l + 1 << '\n';
}
}
L KMP + 猜性质
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2000010;
int ne[N];
signed main()
{
int n; cin >> n;
string s; cin >> s; s = " " +s;
// KMP
for(int i = 2, j = 0; i <= n; i ++)
{
j = ne[i - 1];
while(j && s[i] != s[j + 1]) j = ne[j];
if(s[i] == s[j + 1]) j ++;
ne[i] = j;
}
int mod = n - ne[n];
if(n % mod) cout << 1 << '\n';
else cout << n / mod << '\n';
}
京公网安备 11010502036488号