回家打的第一把，有点拉。
A-Slot
判断一个字符串中字符是不是都是一样的，没什么好说
B-Alcoholic
每瓶酒的容量和浓度为vi和pi，摄入x的时候喝醉。依次喝下每瓶酒，问是否喝醉/第几杯醉。模拟一下即可，注意用浮点数的时候有精度误差。
C-Mandarin Orange
柱形图最大矩形面积，按理说应该是一个单调栈的板子题，但是数据量小，据说可以O(n2)过。
D-Logical Expression
给定N个逻辑与和逻辑或运算，问有2N+1种取值中有多少种可以满足最后的结果为1。
N给的范围是60，不能枚举，所以想一下dp，感觉递推很简单。
$$And: dp[i][0]=2*dp[i-1][0]+dp[i-1][1] dp[i][1]=dp[i-1][1]$$ $$Or: dp[i][0]=dp[i-1][0] dp[i][1]=dp[i-1]+2*dp[i-1][1]$$
其中初始化dp[0][0]=dp[0][1]=1,最终的答案就是dp[n][1]
E-Rotate and Flip
题意：
给定平面上的n(2e5)个点的坐标xi,yi，有m(2e5)个操作，每一次操作有4种：将平面上的点以原点为中心顺时针旋转90°，逆时针旋转90°，以x=p为轴进行轴对称，以y=p为轴进行周对称。然后又q(2e5)个询问，每次询问在第ai次操作后编号为bi的点的位置。
分析：
观察这四种操作对于原来点的坐标的影响：假设原本的点的坐标为(x0,y0),则在这几种操作之后：
$$ 1:(y_0,-x_0) $$ $$ 2:(-y_0,x_0) $$ $$ 3:(2p-x_0,y_0) $$ $$ 4:(x_0,2p-y_0) $$
可以发现，不管怎么操作，x和y前面的系数始终是1和-1，所以我们只需要维护几个标记，包括：是否翻转，xy系数的正负，以及常数项。
（好像题解是用的矩阵变换，算了，差不多吧）
代码：贴一手潘大佬的代码（为什么可以写的这么帅）
1 #include <bits/stdc++.h> 2 #define int long long 3 4 using namespace std; 5 6 #define debug(x) cerr << #x << " = " << x << endl 7 #define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 8 9 #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ‘,‘, ‘ ‘); 10 stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); } 11 12 void err(istream_iterator<string> it) { cout << endl; } 13 14 template <typename T, typename... Args> 15 void err(istream_iterator<string> it, T a, Args... args) { 16 cerr << *it << " = " << a << " "; 17 err(++it, args...); 18 } 19 20 template<typename T> 21 inline void read(T& x) { 22 x = 0; T f = 1; char ch = getchar(); 23 while (!isdigit(ch)) f = (ch == ‘-‘) ? -1 : 1, ch = getchar(); 24 while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); 25 x *= f; 26 } 27 28 template<typename T, typename ...Args> 29 inline void read(T& x, Args&... args) { read(x), read(args...); } 30 31 constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7; 32 33 int n, m, q; 34 int revx, revy; 35 int addx, addy; 36 int swapxy; 37 array<int, MAXN> x, y, a, b; 38 array<int, MAXN> op, p, ansx, ansy; 39 vector<pair<int, int>> vec[MAXN]; 40 41 signed main() { 42 boost; 43 cin >> n; 44 for (int i = 1; i <= n; i++) cin >> x[i] >> y[i]; 45 cin >> m; 46 for (int i = 1; i <= m; i++) { 47 cin >> op[i]; 48 if (op[i] > 2) cin >> p[i]; 49 } 50 cin >> q; 51 for (int i = 1; i <= q; i++) { 52 cin >> a[i] >> b[i]; 53 vec[a[i]].emplace_back(b[i], i); 54 } 55 for (auto& i : vec[0]) { 56 ansx[i.second] = x[i.first]; 57 ansy[i.second] = y[i.first]; 58 } 59 for (int i = 1; i <= m; i++) { 60 if (op[i] == 1) { 61 swapxy ^= 1, revx ^= 1, addx *= -1; 62 swap(revx, revy), swap(addx, addy); 63 } else if (op[i] == 2) { 64 swapxy ^= 1, revy ^= 1, addy *= -1; 65 swap(revx, revy), swap(addx, addy); 66 } else if (op[i] == 3) { 67 revx ^= 1, addx *= -1; 68 addx += p[i] * 2; 69 } else { 70 revy ^= 1, addy *= -1; 71 addy += p[i] * 2; 72 } 73 for (auto& ii : vec[i]) { 74 ansx[ii.second] = x[ii.first]; 75 ansy[ii.second] = y[ii.first]; 76 if (swapxy) swap(ansx[ii.second], ansy[ii.second]); 77 if (revx) ansx[ii.second] *= -1; 78 if (revy) ansy[ii.second] *= -1; 79 ansx[ii.second] += addx; 80 ansy[ii.second] += addy; 81 } 82 } 83 for (int i = 1; i <= q; i++) 84 cout << ansx[i] << " " << ansy[i] << "\n"; 85 return 0; 86 }
F-Sugoroku2
题意：
有n(1e5)+1个格子，从0到n，出发点是0，摇骰子，骰子的点数为1到m(1e5)，摇到多少走多少。中间有k(<=10)个点，若走到上面会返回起点0。问走到终点的期望步数是多少，若不存在则输出-1
分析：
倒着dp，可以知道当i>=n的时候dp[i]=0;并且容易得到：
$$dp[i]=(\sum_{j=i+1}^{i+m}(dp[j]+1)/m)$$
当遇到返回0的点时，dp[i]=dp[0]，代入计算，最后解线性方程
维护一个后缀和，再作差就可以求出这个区间的期望之和以及dp[0]的系数和了
没写代码。。队友过了四舍五入就是我会了（
原文：https://www.cnblogs.com/jinxes6/p/14322132.html
