運氣不錯有個抱枕。
1046 - chess play
題意：
一個n*m的數組，初始全部是’.’，然後3種操作，把一個位置變成’w’，或者把一個位置變成’r’，或者交換兩行。
思路：
vector的swap是O(1)的，直接模拟就行。
//
// main.cpp
// chess play
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>c[];
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
int q;
scanf("%d", &q);
for(int i = ; i <= n; ++i) {
c[i].clear();
for(int j = ; j <= m; ++j)
c[i].push_back();
}
while(q--) {
int t, tt, x, y;
scanf("%d", &t);
if(t == ) {
scanf("%d%d%d", &tt, &x, &y);
if(tt == ) c[x][y] = ;
else c[x][y] = ;
}
else {
scanf("%d%d", &x, &y);
swap(c[x], c[y]);
}
}
for(int i = ; i <= n; ++i) {
for(int j = ; j <= m; ++j) {
if(c[i][j] == ) putchar('.');
else if(c[i][j] == ) putchar('w');
else putchar('b');
}
puts("");
}
}
return ;
}
Best couple
題意：
n個男生，m個女生，然後給一個鄰接表L[i][j]，男生和女生配對的貢獻是他們之間的最短路，問配對的最大貢獻是多少。
思路：
先跑個floyd最短路，本來最大貢獻是不一定是最大比對的，但是因為給的鄰接表是無向圖，不存在這種反例，是以直接費用流就行。
//
// main.cpp
// Best couple
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int N = ;
const int inf = ~>>;
int maz[N][N];
const int M = ;
struct eg{
int u, v, cap, cost;
eg(){}
eg(int a, int b, int c, int d){ u = a, v = b, cap = c, cost = d; };
}edg[M<<];
int fir[M], nex[M<<];
int s, t, ecnt;
void add(int a, int b, int c, int d){
edg[ecnt] = eg(a, b, c, d);
nex[ecnt] = fir[a], fir[a] = ecnt++;
edg[ecnt] = eg(b, a, , -d);
nex[ecnt] = fir[b], fir[b] = ecnt++;
}
int pre[M], dis[N];
int spfa(int s, int t, int n){ //spfa求最小花費增廣路
queue<int>q;
bool vis[N]={};
memset(pre, -, sizeof(pre));
for(int i = ; i <= n; ++i) dis[i] = inf;
dis[s] = ; vis[s] = ;
q.push(s);
while( !q.empty() ){
int u = q.front(); q.pop(); vis[u] = ;
for(int k = fir[u]; k != -; k = nex[k]){
int v = edg[k].v;
if( edg[k].cap && dis[u] + edg[k].cost < dis[v]){
dis[v] = edg[k].cost + dis[u];
pre[v] = k;
if(!vis[v]){
q.push(v);
vis[v] = ;
}
}
}
}
return dis[t] != inf;
}
int mincostEK(int s, int t, int n){ //源點 彙點 總點數
int res = , minflow;
while( spfa(s, t, n)){
minflow = inf;
for(int k = pre[t]; k != -; k = pre[edg[k].u]){
minflow = min(minflow, edg[k].cap); //找到增廣路上的最大可增廣量
}
for(int k = pre[t]; k != -; k = pre[edg[k].u]){
edg[k].cap -= minflow;
edg[k^].cap += minflow;
}
res += dis[t] * minflow; //根據題目修改
}
return res;
}
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while(T--) {
memset(fir, -, sizeof(fir)); ecnt = ;
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n+m; ++i) {
for(int j = ; j <= n+m; ++j) {
scanf("%d", &maz[i][j]);
if(maz[i][j] == -) maz[i][j] = inf;
}
}
s = , t = n+m+;
for(int k = ; k <= n+m; ++k) {
for(int i = ; i <= n+m; ++i) {
for(int j = ; j <= n+m; ++j) {
maz[i][j] = min(maz[i][j], maz[i][k]+maz[k][j]);
}
}
}
for(int i = ; i <= n+m; ++i) {
for(int j = ; j <= n+m; ++j) {
printf("%d ", maz[i][j]);
}
puts("");
}
for(int i = ; i <= n; ++i) {
add(s, i, , );
for(int j = n+; j <= n+m; ++j) {
if(maz[i][j] == inf) continue;
add(i, j, , -maz[i][j]);
}
}
for(int j = n+; j <= n+m; ++j) {
add(j, t, , );
}
int ans = -mincostEK(s, t, t+);
printf("%d\n", ans);
}
return ;
}
1048 - Best substring
題意：
給一個字元串，然後val[i]表示以i為中心的最長回文子串的長度，然後求一個子串，滿足 ∑leni=1(−1)k+1∗i∗val[k] 最大，其中k是i在原串中的位置。
簡單的說就是給一個數組，然後去掉一個字首和字尾（可能為空），要求 ∑leni=1i∗a[i] 最大。
思路：
先跑馬拉車求出val數組，然後推一下發現可以斜率優化，就是這個題。
//
// main.cpp
// Best substring
//
// Created by 翅膀 on //.
// Copyright © 年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = e5+;
char str[N];
char s[N*2];
int sl[N*2]; //p[i]表示以i為中軸的最長回文長度
void manacher(char *str, int len){
memset(sl, , sizeof(sl));
int id = ;
for(int i = len; i >= ; --i){
s[*i+] = str[i];
s[*i+] = '#';
}
s[] = '$', s[*len+] = '\0';
int up = *len+;
for(int i = ; i < up; ++i){
if(sl[id] + id > i) sl[i] = min(sl[*id-i], sl[id]+id-i);
else sl[i] = ;
while(s[i-sl[i]] == s[i+sl[i]]) ++sl[i];
if(id+sl[id] < i+sl[i]) id = i;
}
}
ll val[N], sum[N], p[N];
int q[N], tail, top;
inline ll y(int x){ return p[x] - x*sum[x]; }
double g(int j, int k){
double dy = y(j) - y(k);
double dx = j - k;
return dy/dx;
}
inline ll getans(int i, int j){
return p[i] - p[j] - j*(sum[i] - sum[j]);
}
int solve(ll x){
int l = top, r = tail-, mid, res = l;
while(l <= r){
mid = (l+r) >> ;
if(g(q[mid], q[mid-1]) < -x) l = mid+, res = mid;
else r = mid-;
}
return q[res];
}
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d %s", &n, str);
manacher(str, n);
for(int i = ; i <= n; ++i) {
val[i] = sl[i*2]-;
if(i%2 == ) val[i] *= -;
}
for(int i = ; i <= n; ++i) {
sum[i] = sum[i-]+val[i];
p[i] = p[i-] + i*val[i];
}
top = tail = ;
q[tail++] = ;
ll ans = ;
for(int i = ; i <= n; ++i){
int j = solve(sum[i]);
ans = max(ans, getans(i,j));
while(top < tail- && g(i, q[tail-1]) < g(q[tail-1], q[tail-2])) tail--;
q[tail++] = i;
}
printf("%lld\n", ans);
}
return ;
}
1049 - Deg-route
題意：
求從(0,0)走到(x,y)，其中x>=y，且不穿過y=x的方案數。
思路：
考慮從(0,0)走到(x,y)且穿過y=x的方案數，設為l(x,y)。
那麼考慮第一次穿過的位置，設為(q,q)。
當周遊q從0到y-1時，方案數是不重不漏的，因為每種方案必然有第一次穿過的位置，且位置唯一。
設Cat(i)表示第i個卡特蘭數，我們知道卡特蘭數是(0,0)走到(i,i)不經過y=x的路徑數，那麼就可以表示出l(x,y)了。
l(x,y)=∑i=0y−1Cat(i)∗Cx−ix−i+y−i−1
這個式子的意思是枚舉第一次穿過的點(i,i)然後走到這個點的方案數乘上這個點往上走了一步之後，再任意走到(x,y)的方案數。
這個式子的解：
l(x,y)=Cx+1x+1+y−1
也就是說等價于從(-1,1)走到(x,y)的方案數，我們來從組合學分析一下就知道，這是個十分優美的結論。
首先條件是隻能往x和y的正半軸走，并且要求穿過y=x。
穿過y=x并不是直覺的條件，考慮到穿過的那一步必須是往上走的，那麼穿過y=x就等價于與y=x+1相交或者相接觸，此時根據x>=y，(x,y)是與y=x+1相離的。
注意到(-1,1)與(0,0)關于y=x+1對稱，那麼從(-1,1)走到(x,y)，是必然接觸y=x+1的，因為(-1,1)與(x,y)分别處于y=x+1分割的兩個半平面内，假設一條路徑與y=x+1的交點是(p,p+1)，在相交之前走的路徑，我們總可以找到一條從(0,0)到(p,p+1)的路徑與之對應，根據對稱性：
當(-1,1)出發的路徑往上走，那麼(0,0)出發的路徑就往右走。
當(-1,1)出發的路徑往右走，那麼(0,0)出發的路徑就往上走。
當(0,0)走到了(p,p+1)，之後的路就按照(-1,1)的走法走就行了。
容易證明這是不重不漏，一一對應的，這樣我們就給出了一個組合學的解釋，從(0,0)走到(x,y)穿過y=x的方案數等價于從(-1,1)走到(x,y)的方案數。
那麼最後答案就是總的減去不合法的：
ans=Cxx+y−Cx+1x+1+y−1
因為模數較小，lucas即可。
//
// main.cpp
// Deg-route
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MX = ;
const ll mod = +;
ll fac[MX];
ll pow_mod(ll a, ll k) {
ll res = ;
while(k) {
if(k&) res = (res*a)%mod;
a = (a*a)%mod;
k >>= ;
}
return res;
}
ll C(ll n, ll k){
if(n < k || n < || k < ) return ;
return fac[n]*pow_mod(fac[n-k]*fac[k]%mod, mod-)%mod;
}
ll lucas(ll a, ll b){
if(b == ) return ;
return lucas(a/mod, b/mod) * C(a%mod, b%mod) % mod;
}
void init(){ //初始化階乘
fac[] = fac[] = ;
for(int i = ; i <= mod; ++i) fac[i] = fac[i-]*i%mod;
}
int main(int argc, const char * argv[]) {
init();
int T;
scanf("%d", &T);
while(T--) {
int x, y;
scanf("%d %d", &x, &y);
printf("%lld\n", (lucas(x+y, x)-lucas(x+y, x+)+mod)%mod);
}
return ;
}
1050 - array
題意：
給一個數組a，問有多少個子序列滿足第一個數是1，後一個是前一個的兩倍。
思路：
直接dp，dp[i]表示以i結尾的子序列個數，另外用個pre[i]表示2^i的個數。
//
// main.cpp
// array
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
typedef long long ll;
const int N = +;
const ll mod = +;
ll a[N];
ll dp[N], pre[];
int aa[N];
map<ll, int>cnt;
int check(ll x) {
if((x&(x-)) != ) return -;
return cnt[x];
}
int main(int argc, const char * argv[]) {
cnt[] = ;
for(int x = , i = ; i <= ; i <<= , ++x) {
cnt[i] = x;
}
int T;
scanf("%d", &T);
while(T--) {
memset(dp, , sizeof(dp));
memset(pre, , sizeof(pre));
int n;
scanf("%d", &n);
for(int i = ; i <= n; ++i) {
scanf("%lld", a+i);
aa[i] = check(a[i]);
}
ll ans = ;
for(int i = ; i <= n; ++i) {
int tmp = aa[i];
if(tmp == ) dp[i] = ;
else dp[i] = pre[tmp-];
pre[tmp] = (pre[tmp]+dp[i])%mod;
ans = (ans+dp[i])%mod;
}
printf("%lld\n", ans);
}
return ;
}
1051 - My-graph
題意：
問n個點的圖能不能構造出原圖和補圖同構的圖。
思路：
滿圖有n*(n-1)/2條邊，至少邊數要是偶數，猜了一發過了，實際上這是個充要條件。
//
// main.cpp
// My-graph
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
if((n*(n-)/)% == ) puts("no");
else puts("yes");
}
return ;
}
1052 - See car
題意：
一個人站在(a,b)，然後他的右下方有一些點，問你能看到的點的數量。
思路：
存下斜率就行。
//
// main.cpp
// See car
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <set>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b? gcd(b, a%b) : a; }
struct dom{
ll up, down;
void loli() {
ll tmp = gcd(up, down);
up /= tmp, down /= tmp;
}
dom(ll a, ll b) { up = a, down = b; loli(); }
bool operator < (const dom& z) const {
return up*z.down < z.up*down;
}
};
set<dom>st;
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while(T--) {
ll a, b, n;
scanf("%lld%lld%lld", &a, &b, &n);
st.clear();
for(ll x, y, i = ; i <= n; ++i) {
scanf("%lld %lld", &x, &y);
st.insert(dom(y-b, x-a));
}
printf("%lld\n", (ll)st.size());
}
return ;
}
1053 - Gemstone digger
題意：
n個寶藏，去第i個地方有a[i]個寶藏，在i采寶藏的死的機率是pi，每個地方互相獨立，問存活率>0.19的情況下最多采多少個寶藏。
思路：
dp[i][j]表示前i個寶藏中一共采了j個時最大的存活率是多少。
dp[i][j] = dp[i-1][j];
if(j >= a[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-a[i]]*(1-pi))
跑完後掃一遍找存活率大于0.19的最多寶藏。
//
// main.cpp
// Gemstone digger
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[];
double p[];
double dp[][];
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while(T--) {
int n;
int tot = ;
scanf("%d", &n);
for(int i = ; i <= n; ++i) {
scanf("%d", a+i);
tot += a[i];
}
for(int i = ; i <= n; ++i) {
scanf("%lf", p+i);
}
memset(dp, , sizeof(dp));
dp[][] = ;
for(int i = ; i <= n; ++i) {
for(int j = ; j <= tot; ++j) {
if(j >= a[i]) dp[i][j] = max(dp[i-][j], dp[i-][j-a[i]]*(-p[i]));
else dp[i][j] = dp[i-][j];
}
}
int ans = ;
for(int i = ; i <= n; ++i) {
for(int j = ; j <= tot; ++j) {
if(dp[i][j] > ) ans = max(ans, j);
}
}
printf("%d\n", ans);
}
return ;
}
1054 - String cut
題意：
給一個字元串，可以删一個字元，删完後要求串是由一個子串重複k次構成的，求最大的k。
思路：
字元串不會做，待隊友補。
1055 - Ball-box
題意：
一個盒子一開始有n個球，每個球标号唯一，先執行操作1，如果兩個球x,y滿足|x-y|不在盒子裡，那麼久把|x-y|放進去，設操作次數為p1，然後執行操作2，不斷摸球，直到所有球都被摸過，設操作次數為p2，求p1+p2的期望。
思路：
如果兩個球x,y在盒子裡，設x>=y，那麼gcd(x,y) == gcd(x,x-y)，可以推出最後所有數的gcd等價于一開始所有數的gcd，那麼操作1的次數就是最大的數/gcd。
操作2的次數容易推導，設dp[i]表示已經摸了i個球，直到摸完所有球的期望次數。顯然有 dp[n]=0，dp[i]=i/n∗dp[i]+(n−i)/n∗dp[i+1]+1
化簡下dp[n] = 0, dp[i] = dp[i+1]+n/i。
那麼dp[0] = n*Hn，其中Hn是調和級數。
然後算就行了。
注意需要特判0。
//
// main.cpp
// Ball-box
//
// Created by 翅膀 on 16/11/5.
// Copyright © 2016年 kg20006. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = ;
int gcd(int a, int b) { return b? gcd(b, a%b) : a; }
int a[N];
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while(T--) {
int n, mx = -, zr = ;
scanf("%d", &n);
for(int i = ; i <= n; ++i) {
scanf("%d", a+i); mx = max(mx, a[i]);
if(a[i] == ) zr = ;
}
int tmp = a[];
for(int i = ; i <= n; ++i) {
tmp = gcd(tmp, a[i]);
}
int tot = mx/tmp+zr;
double ans = ;
for(int i = ; i <= tot; ++i) {
ans += *tot/i;
}
ans += (tot-n);
printf("%d\n", (int)ans);
}
return ;
}
![CF1394C 計算幾何[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)