Day1
分析：
貪心即可，從最高位開始掃，找1
/*
對于2進制，越高位有1，則數字越大。
算法思想：
此題本質就是統計序列中每一個2進制位上是1的數的個數是否大于2個，若大于2個則意味着
最終該位&的結果，其該位上一定是1.那麼按照從高位到低位來依次處理就可以解決。
算法步驟：
從最高位到最低位（i = 30 ~ 0）依次枚舉判斷：
1、判斷目前第 i 位上是 1 的數并統計記錄下來，為節省空間，可以複用原數組（覆寫）來記錄産生的新序列，
即把第 i 位不是 1 的數全部舍棄，隻保留第 i 位是 1 的數；
2、從上面記錄産生的新序列中（即第i位都是1的數），繼續按照上述辦法來處理第i+1位，直到判斷完最後一位（i=0）；
3、最後統計
*/
#include<cstdio>
using namespace std;
int n,a[300002],d[35] = {0},ans = 0; //2^30>1000000000
void init(){
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
}
void find(){
int i, j, ct, now = n, t;
for(i = 30; i >= 0; i--){
ct = 0;
for(j = 1; j <= now; j++)
if(a[j] & (1 << i)) ct++; //統計第i位是1的數有多少個
if(ct < 2) continue; //目前第 i 位是1的數不夠2個，則直接枚舉第 i+1 位
t = 0; d[i] = 1; //d[i]的作用标記有兩個以上的數第i位是1
for(j = 1; j <= now; j++)
if(a[j] & (1 << i)) a[++t] = a[j]; //把第 i 位是1的數全部儲存在a[1]~a[t]中（節省空間，直接覆寫原數組）
now = t; //繼續在a[1]~a[t]中判斷第 i+1 位的情況
}
for(i = 30; i >= 0; i--)
if(d[i]) ans = ans ^ (1 << i); //ans初始化為0，用異或運算，可保證第 i 位是 1。
printf("%d\n",ans);
}
int main()
{
freopen("and.in","r",stdin);
freopen("and.out","w",stdout);
init(); find();
return 0;
}
簡單的數學期望的題
/*
分析：一個物品會被染色的機率為 1/2，用某種顔色染色的機率為 1/c。
1、40分的方程是用f[i][j][k]表示第i個物品在j次操作次數後顔色變為 k的機率，時間複雜度大概是O(T*N*K*c^2)
2、60分要考慮到所有物品具有相似性，即 n個物品本質是相同的，是以不用枚舉物品。
f[i][j]表示一個物品操作 i次顔色變為 j的機率。
滿足： f[i+1][j] += f[i][j]*(1/2)
f[i+1][(j*b)%c]+=f[i][j]*[(1/2)*(1/c)]
初始值f[0][1]=1，答案就是Σf[i][j]*j (i表示該箱子的操作次數,0 <= j<c)。複雜度O（T*K*c^2）
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 55
using namespace std;
int T, n, c, K, cs[MAXN], maxc;
double f[MAXN][MAXN << 1], ans;
void init(){
scanf("%d%d%d",&n, &c, &K);
int x, y;
memset(cs,0,sizeof(cs));
maxc = 0;
for(int i = 1; i <= K; i++){
scanf("%d%d",&x, &y);
for(int j = x; j <= y; j++){
cs[j]++; //統計 j 号箱子選擇了幾次
maxc = max(maxc,cs[j]); //記錄所有箱子裡選擇次數最多的(即最多的操作次數)
}
}
}
void dp(){
memset(f, 0, sizeof(f));
f[0][1] = 1;
for(int i = 0; i < maxc; i++)
for(int j = 0; j < c; j++){
f[i+1][j] += f[i][j]/2;
for(int k = 0; k < c; k++)
f[i + 1][(j * k) % c] += f[i][j] / (2 * c);
}
ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 0; j < c; j++)
ans += f[cs[i]][j] * j; //所有箱子顔色編号和的期望值
printf("%.9lf\n", ans);
}
int main()
{
freopen("elephant.in","r",stdin);
freopen("elephant.out","w",stdout);
scanf("%d", &T);
while(T--){
init();
dp();
}
fclose(stdin);
fclose(stdout);
return 0;
}
最短路的闆子，多了一個k，SPFA跑動規。
/*
此題本質：分層圖的最短路。
K=1時可以考慮将一點拆成兩點。
兩層分别按原圖建圖，然後在第一層向第二層中對應的點連一條長度為 0的單向邊；
例如原圖有一條 1到 2的雙向邊。将 1拆成 1和 1+n，2同理；
然後分别在 1、2和 1+n、2+n之間建原長度的雙向邊；
然後分别在 1、2+n和 2、1+n之間建一條長度為 0的單向邊，這樣的圖能保證至多跑一次長度為 0的邊。
在點數邊數較少的情況下，K大到 3,4應該也能卡過。
至于正解，可以用一個二維的 dis數組跑最短路，dis[i][j]——表示到達 i點，用了j次急救包的最少流血量。
用最短路做一個類似于dp的東西。答案為dis[T][K].
注意：裸跑spfa會 T三個點，若寫spfa記得加 SLF優化。
SLF優化——spfa的SLF優化就是 small label first 優化；
當加入一個新點v的時候如果此時的dis[v]比隊首dis[q.front()]還要小的話，就把v點加入到隊首，
否則把他加入到隊尾，因為先擴充最小的點可以盡量使程式盡早的結束，一種方法可以用模拟隊列，
head，tail，但是由于不知道q的數組開多大，可用雙端隊列 deque<int> q 。
spfa的SLF優化模闆：
void spfa(int s)
{
deque<int>q;
memset(dis,inf,sizeof(dis));
memset(use,0,sizeof(use));
dis[s]=0;
q.push_back(s);
use[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop_front();
use[u]=0;
for(int i=0;i<(int)edge[u].size();i++)
{
int v=edge[u][i].v;
if(dis[v]>dis[u]+edge[u][i].w)
{
dis[v]=dis[u]+edge[u][i].w;
if(!use[v])
{
use[v]=1;
if(!q.empty()&&dis[v]<dis[q.front()])
q.push_front(v);
else
q.push_back(v);
}
}
}
}
}
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define MAXN 10002
using namespace std;
int n, m, K, S, T, zz, head[MAXN];
struct bian{
int to, nx, v;
} e[MAXN * 10];
struct dui{
int w,c;
} q[MAXN * 10];
int dis[MAXN][12], pd[MAXN][12], ans;
void insert(int x,int y,int z){ //鄰接表
zz++; e[zz].to = y; e[zz].v = z; e[zz].nx = head[x]; head[x] = zz;
zz++; e[zz].to = x; e[zz].v = z; e[zz].nx = head[y]; head[y] = zz;
}
void init()
{
scanf("%d%d%d", &n, &m, &K);
scanf("%d%d",&S, &T);
int x,y,z;
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &x, &y, &z);
insert(x, y, z);
}
}
void spfa()
{
int t = 0, w = 1, x, ct, p;
memset(dis, 127, sizeof(dis));
q[0].w = S; q[0].c = 0; dis[S][0] = 0; pd[S][0] = 1;
while(t != w) {
x = q[t].w; ct = q[t].c; t = (t + 1) % 100000;
for(int i = head[x]; i; i = e[i].nx){
p = e[i].to;
if(dis[p][ct] > dis[x][ct] + e[i].v){
dis[p][ct] = dis[x][ct] + e[i].v;
if(!pd[p][ct]){
if(dis[p][ct] < dis[q[t].w][q[t].c]){
t = (t + 100000 - 1) % 100000;
q[t].w = p; q[t].c = ct; pd[p][ct] = 1;
}
else{
q[w].w = p; q[w].c = ct; pd[p][ct] = 1; w = (w + 1) % 100000;
}
}
}
if(ct + 1 <= K && dis[p][ct + 1] > dis[x][ct]){
dis[p][ct + 1] = dis[x][ct];
if(!pd[p][ct + 1]){
if(dis[p][ct + 1] < dis[q[t].w][q[t].c]){
t = (t + 100000 - 1) % 100000;
q[t].w = p; q[t].c = ct + 1; pd[p][ct+1] = 1;
}
else{
q[w].w = p; q[w].c = ct + 1; pd[p][ct+1] = 1; w = (w + 1) % 100000;
}
}
}
}
pd[x][ct] = 0;
}
ans = 1 << 30;
for(int i = 0; i <= K; i++)
ans = min(ans, dis[T][i]);
printf("%d\n",ans);
}
int main()
{
freopen("move.in","r",stdin);
freopen("move.out","w",stdout);
init(); spfa();
return 0;
}
Day2
倒着跑，沒想到吧。
/*
考慮最後一行，因為其代表檔案結束，是以解密後的a=b=c=0。那麼我們可以知道倒數第二行的答案（LastAns=-a=-b=-c）。
那麼原始式子即轉換成一個簡單的三元一次式子（隻和a,b,c有關），然後這解密後的值又可以由上一行的答案和輸入的a0,b0,c0得到，
于是就變成了一個隻和LastAns有關系的一進制一次式子，是以又可以得到了上一行的答案。是以這樣一直算回去就好了。
*/
#include <cstdio>
using namespace std;
int n, cnt, top, ans;
int v[50005], res[500005];
int a[500005], b[500005], c[500005];
int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f=-1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int main()
{
freopen("seq.in", "r", stdin);
freopen("seq.out", "w", stdout);
n = read();
for(int i =1 ; i <= n; i++)
v[i] = read();
cnt = 1;
while(scanf("%lld%lld%lld", &a[cnt], &b[cnt], &c[cnt]) != EOF)
cnt++;
cnt--;
top = 0;
res[++top] = ans = -a[cnt--];
for(int k = cnt; k; k--)
{
int xi = v[ans], i = ans;
int t1 = a[k] * (i + 1) * xi * xi + (b[k] + 1) * i * xi + (c[k] + i);
int t2 = (i + 1) * xi * xi + i * xi + 1;
ans = -t1 / t2;
res[++top] = ans;
}
for(int i = top - 1; i; i--) printf("%lld\n", res[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
組合數學，好好推一下就OK了。
/*
首先頭尾連續的無油漆桶段和兩個相同顔色油漆桶間的段落不影響答案，去掉不考慮。
然後對于任意兩個連續的油漆桶中的段落（假設坐标分别為a,b）可以有b-a種油漆方案，
則所有段落的方案數乘積即為所求。
*/
#include <cstdio>
#include <algorithm>
#define mod 1000000009
#define ll long long
using namespace std;
ll ans = 1;
int n, m;
struct data{
int val, pos;
} a[100005];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
bool operator <(data a, data b)
{
return a.pos < b.pos;
}
int main()
{
freopen("paint.in", "r", stdin);
freopen("paint.out", "w", stdout);
n = read(); m = read();
for(int i = 1; i <= m; i++)
{
char ch[2];
scanf("%s", ch);
a[i].val = ch[0]-'A';
a[i].pos = read();
}
sort(a + 1, a + m + 1);
for(int i = 2; i <= m; i++)
if(a[i].val != a[i-1].val)
ans = ans * (a[i].pos - a[i - 1].pos) % mod;
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
差分限制的闆子（不會差分限制的我部落格裡看）
/*
很明顯的差分限制系統的題目。
如果A和B距離至多為 D則建邊 A->B權值為 D，距離至少為 D則建邊 B->A權值為 -D。
然後最短路。若有負權環則輸出-1，若無法到達點 N則輸出-2，否則直接輸出1~N的距離即可。
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf (1LL<<60)
#define ll long long
using namespace std;
int n, ml, md, cnt;
int t[1005], last[1005], fa[1005], q[1005];
ll dis[1005];
bool inq[1005];
struct data{
int to, next, v;
} e[40005];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void insert(int u,int v,int w)
{
e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w;
}
int spfa()
{
for(int i = 1; i <= n; i++) dis[i] = inf;
int head = 0, tail = 1;
q[0] = 1; t[1]++; dis[1] = 0;
while(head != tail)
{
int now = q[head]; inq[now] = 0; head++;
if(head == 1002) head = 0;
for(int i = last[now]; i; i = e[i].next)
if(dis[now] + e[i].v < dis[e[i].to])
{
t[e[i].to]++;
if(t[e[i].to] == n + 1) return 0;
dis[e[i].to] = dis[now] + e[i].v;
if(!inq[e[i].to])
{
inq[e[i].to] = 1;
q[tail++] = e[i].to;
if(tail == 1002) tail = 0;
}
}
}
return 1;
}
int main()
{
freopen("layout.in", "r", stdin);
freopen("layout.out", "w", stdout);
n = read(); ml = read(); md = read();
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= ml; i++)
{
int a = read(), b = read(), d = read(); d = abs(d);
insert(a, b, d);
}
for(int i = 1; i <= md; i++)
{
int a = read(), b = read(), d = read(); d = abs(d);
insert(b, a, -d);
}
if(!spfa()) puts("-1");
else if(dis[n] == inf) puts("-2");
else printf("%lld\n",dis[n]);
fclose(stdin);
fclose(stdout);
return 0;
}