【hnoi2010】
これらのものは出しても悪くない.
未完待機=.=......
chrous:
标题:ややアホなXdpは、2つの状態f[i,j],g[i,j]を直接設計し、それぞれi~jを形成する一段を表し、最後に最も左/最も右の案数に置き、直接移行すればよい.
planar:
題意:図のハミルトニアン回路とすべてのエッジを与え、平面図である可能性があるかどうかを尋ねる.点n<=200、辺m<=1000000100のデータ群.
タイトルで与えられたハミルトニアンループを利用します(ハミルトニアンパスだけが必要です)
ハミルトニアン経路を「まっすぐ引っ張る」ことを想像すると、残りのすべての辺は必ず経路の両側に分かれている.
もし2つの辺が同じ側に置くと交差するならば、彼らは必ず異側に置いて、最後に矛盾しているかどうかを判断します.
2-satは、簡単な調査セットでもこの問題を解決することができます.
唯一の問題はo(m^2)の列挙エッジが交差するのが遅すぎるかどうかであり,適切な方法を見つけて最適化しようとしたが,結果は.......結果は......元平面図o(m)=o(n)(ピットされた=.=!)、実際m<=3*n-6=.=!,では、判決を下すと、直接裸でいいです!
fsk:まだ=していません.=!......テーマはすべて木有懂=.
bus:
标题:道路には1~n駅、kバス、1~kが彼らの起点駅、n-k+1~nが重点駅です.バスは番号の小さい駅から番号の大きい駅に向かって、1つの駅に1つのバスが止まっていて、1つのバスに対して、それが止まっている任意の2つの駅の間で、番号の距離はpを超えてはいけません;
K,p <= 10, n <=10^9;
nはかなり大きくて、kはかなり小さくて、考えなくても形のモーメントに乗った=.=!
しかし、この距離の現在の距離を直接記録すると、情報量soが大きくなる.
バスは差がないことに気づいたので、現在位置p以内のすべてのバスからの距離を記録するだけでいいのですが...ちょっと回ります.
いずれにしても状態はC(9,5)以内に圧縮され,圧縮モーメントに乗じることができる.
stone:
題意:n堆石を与えて、いくつかの堆石が取り外されたことを実現して、2人はゲームをして石を取って、1堆の石が取られて、その左あるいは右のものが取り外されただけです.前後の手でそれぞれどれだけの石が行けるかを聞く.
この問題を見て、見覚えがあるようです.去年の試験でこの問題が出たようですが、その時は劉尧先生の説明を聞いてやっと分かりました.最後にもめまいがしました.
よく考えてみると大体考えを思い出し、両選手の石数の差を集計した.取った石はこのシーケンスをいくつかのブロックに分けて、最も理想的な状況は:
↗, ↘↗,….., ↘↗, ↘,このような状況は直接欲張るだけでOKです.
しかし、状況は複雑になるに違いないが、修復できる.
について↘↗破壊される↘または↗見なすこともできる↘↗), きっと現れた↗↘の場合、すなわちa[i-1]a[i+1]であり、この場合、「先手」は必ずa[i-1]とa[i+1]を取り、後手は必ずa[I]を取り、このようにして、3つの数をa[i+1]+a[i-1]-a[i]にまとめることができる.左右の↗および↘, それぞれ↘,↗「先手」は必ず損をするので、みんなが先に取りたくないので、必ず最後まで残しておきます.では、誰が先に取ったかを推定することができます.そうすれば、事前に統計することができ、最後の石について、順番に1つずつ取ることができます.
city
......
Bounce:
題意:与えられたシーケンスk[n]、2つの操作、1つの修正操作、ある位置のkを修正し、1つの質問操作、i位置から質問し、i+k[I]にジャンプするたびに、最後に何回ジャンプしてシーケンスから飛び出すことができるかを聞く.
正解はダイナミックツリーを使いますが、結局恥知らずにチェーン水で渡りました.
kをsqrt(n)に分けて、各位置がそのブロックから飛び出すステップ数と飛び出す場所を統計して、このように各質問はsqrt(n)レベルで、速度はやっと強いです;
Matrix:
标题:与えられたb[N][N],b[I][J]=a[i][j]+a[i-1][j]+a[i][j-1]+a[i-1][j-1]辞書の順序の最小のAを求めます
Aの元素は10を超えず、n<=200である.
この問題は恥知らずに他の人のb,aと補助配列cに関する公式を写した.
Ai,j= Ci,j + (-1)^i+j-2 *A1,1 + (-1)^i-1*A1,j + (-1)^j-1*Ai,1 (i>1,j>1)
ここでc[I][J]=B[I][J]-C[I-1][J]-C[I][J-1]-C[I-1][J-1];
では、最初の行の数値を検索し、最初の列の値範囲を維持し、矛盾が発生したら枝を切ることで検索できます.
ツッコミ:公式は他人のものを写して、結局その公式の指数は意外にも間違っていて、TAT、結果はずっと調整していないで、wa、wa、wa、wa............最後に手で計算して検査してやっと公式の指数が間違っていることを発見しました=!、人のスタイルを写すのは本当にいい習慣ではない.
未完待機=.=......
chrous:
标题:ややアホなXdpは、2つの状態f[i,j],g[i,j]を直接設計し、それぞれi~jを形成する一段を表し、最後に最も左/最も右の案数に置き、直接移行すればよい.
# include <cstdlib>
# include <cstdio>
# include <cmath>
using namespace std;
const int mo = 19650827, maxn = 1000+10;
int f[maxn][maxn], g[maxn][maxn];
int i, j, l, r, n, h[maxn];
int main()
{
freopen("chorus.in", "r", stdin);
freopen("chorus.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &h[i]);
for (i = 1; i <= n; i++) f[i][i] = 1;
for (r = 2; r <= n; r++)
for (l = r-1; l >= 1; l--)
{
f[l][r] = ((h[l]<h[l+1])*f[l+1][r] + (h[l]<h[r])*g[l+1][r]) % mo;
g[l][r] = ((h[r]>h[l])*f[l][r-1] + (h[r]>h[r-1])*g[l][r-1]) % mo;
}
printf("%d", (f[1][n]+g[1][n])% mo);
return 0;
}
planar:
題意:図のハミルトニアン回路とすべてのエッジを与え、平面図である可能性があるかどうかを尋ねる.点n<=200、辺m<=1000000100のデータ群.
タイトルで与えられたハミルトニアンループを利用します(ハミルトニアンパスだけが必要です)
ハミルトニアン経路を「まっすぐ引っ張る」ことを想像すると、残りのすべての辺は必ず経路の両側に分かれている.
もし2つの辺が同じ側に置くと交差するならば、彼らは必ず異側に置いて、最後に矛盾しているかどうかを判断します.
2-satは、簡単な調査セットでもこの問題を解決することができます.
唯一の問題はo(m^2)の列挙エッジが交差するのが遅すぎるかどうかであり,適切な方法を見つけて最適化しようとしたが,結果は.......結果は......元平面図o(m)=o(n)(ピットされた=.=!)、実際m<=3*n-6=.=!,では、判決を下すと、直接裸でいいです!
# include <cstdlib>
# include <cstdio>
# include <cmath>
# include <cstring>
using namespace std;
const int maxn = 10000 + 5;
int ufs[maxn*4], rel[maxn*4];
int g[maxn], x[maxn*4], y[maxn*4], tmp;
int n, m;
int find (int x)
{
int y;
if (ufs[x] == x) return x;
else {
y = find(ufs[x]);
rel[x] = rel[x] ^ rel[ufs[x]];
return ufs[x] = y; };
}
bool work()
{
int fi, fj, i, j, k;
for (i = 1; i<= m; i++) if (g[x[i]] > g[y[i]]) tmp = x[i], x[i] = y[i], y[i] = tmp;
for (i = 1; i<= m; i++) ufs[i] = i, rel[i] = 0;
for (i = 1; i<= m; i++)
for (j = 1; j <= m; j++)
if (i != j)
if (g[x[i]] < g[x[j]] && g[x[j]] < g[y[i]] && g[y[i]] < g[y[j]])
{
fi = find(i); fj = find(j);
if (fi != fj) ufs[fi] = fj, rel[fi] = 1^rel[i]^rel[j];
else if ((rel[i]^rel[j]) == 0)
return false;
}
return true;
}
int main()
{
int test, i, k;
freopen("planar.in", "r", stdin);
freopen("planar.out", "w", stdout);
scanf("%d", &test);
for (int ssss = 1; ssss <= test; ssss++)
{
scanf("%d%d", &n, &m);
memset(g, 0, sizeof(g));
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
memset(ufs, 0, sizeof(ufs));
memset(rel, 0, sizeof(rel));
int xx, yy, now = 0;
for (i = 1; i<= m; i++)
{
scanf("%d%d", &xx, &yy);
if (xx != yy)x[++now]=xx, y[now]=yy;
}
m = now;
for (i = 1; i<= n; i++)
{
scanf("%d", &k);
g[k] = i;
};
if (m > 3*n) printf("NO
");
else if (work()) printf("YES
"); else printf("NO
");
}
return 0;
}
fsk:まだ=していません.=!......テーマはすべて木有懂=.
bus:
标题:道路には1~n駅、kバス、1~kが彼らの起点駅、n-k+1~nが重点駅です.バスは番号の小さい駅から番号の大きい駅に向かって、1つの駅に1つのバスが止まっていて、1つのバスに対して、それが止まっている任意の2つの駅の間で、番号の距離はpを超えてはいけません;
K,p <= 10, n <=10^9;
nはかなり大きくて、kはかなり小さくて、考えなくても形のモーメントに乗った=.=!
しかし、この距離の現在の距離を直接記録すると、情報量soが大きくなる.
バスは差がないことに気づいたので、現在位置p以内のすべてのバスからの距離を記録するだけでいいのですが...ちょっと回ります.
いずれにしても状態はC(9,5)以内に圧縮され,圧縮モーメントに乗じることができる.
# include <cstdlib>
# include <cstdio>
# include <cmath>
# include <cstring>
using namespace std;
const int size = 130, mo = 30031;
bool a[size][20];
int t[size][size], ml[size][size], c[size][size];
int top = 1, n, kn, p;
void dfs(int have, int past)
{
int i;
if (have == kn)
{
top++;
for (i = 1; i <= kn; i++) a[top][i] = a[top-1][i];
}
else
for (i = past+1; i <= p; i++)
{
a[top][i] = true;
dfs(have+1, i);
a[top][i] = false;
}
}
void prepare()
{
int flag ; int i, j, k;
for (i = 1; i <= top; i++)
for (j = 1; j <= top; j++)
{
flag = 1;
for (k = 1; k <= p; k++)
if ((a[i][k]^a[j][k+1])) flag --;
if (flag == 0) c[i][j] = ml[i][j] = 1;
}
}
void mul(int c[size][size], int a[size][size], int b[size][size])
{
int i, j, k;
memset(t, 0, sizeof(t));
for (i = 1; i <= top; i++)
for (j = 1; j <= top; j++)
for (k = 1; k <= top; k++)
t[i][j] = (t[i][j]+a[i][k]*b[k][j]) % mo;
for (i = 1; i <= top; i++)
for (j = 1; j <= top; j++)
c[i][j] = t[i][j];
}
int main()
{
freopen("bus.in", "r", stdin);
freopen("bus.out", "w", stdout);
scanf("%d%d%d", &n, &kn, &p);
a[top=1][1] = true; dfs(1, 1);
top--;prepare();
for (n-=kn+1; n >0; n >>=1, mul(ml,ml,ml))
if (n & 1) mul(c,c,ml);
// for (n-=kn+1; n >0; n--)
// mul(c,c,ml);
printf("%d", c[1][1]);
return 0;
}
stone:
題意:n堆石を与えて、いくつかの堆石が取り外されたことを実現して、2人はゲームをして石を取って、1堆の石が取られて、その左あるいは右のものが取り外されただけです.前後の手でそれぞれどれだけの石が行けるかを聞く.
この問題を見て、見覚えがあるようです.去年の試験でこの問題が出たようですが、その時は劉尧先生の説明を聞いてやっと分かりました.最後にもめまいがしました.
よく考えてみると大体考えを思い出し、両選手の石数の差を集計した.取った石はこのシーケンスをいくつかのブロックに分けて、最も理想的な状況は:
↗, ↘↗,….., ↘↗, ↘,このような状況は直接欲張るだけでOKです.
しかし、状況は複雑になるに違いないが、修復できる.
について↘↗破壊される↘または↗見なすこともできる↘↗), きっと現れた↗↘の場合、すなわちa[i-1]
# include <cstdlib>
# include <cstdio>
using namespace std;
const long long oo= (long long)1 << 62;
const int maxn = 1000000+200;
long long sum, ans;
long long a[maxn], b[maxn];
int n, tot, next[maxn], pred[maxn];
long long tmp;
void del(int v)
{
next[pred[v]] = next[v];
pred[next[v]] = pred[v];
}
void maintain(int p)
{
if ((a[p] != -oo && a[pred[p]] != -oo && a[next[p]]!= -oo) &&(a[p] >= a[pred[p]] && a[p] >= a[next[p]]))
{
a[p] = a[pred[p]] + a[next[p]] - a[p]; a[pred[p]] = a[next[p]] = -oo;
del(pred[p]); del(next[p]);
maintain(pred[p]); maintain(p); maintain(next[p]);
}
}
void change(int i, int j)
{
for (;b[i] != -oo && b[i+j] != -oo && b[i] > b[i+j]; b[i]=b[i+j]=-oo, i+=2*j)
if (!(tot & 1)) ans += b[i+j]-b[i]; else ans -= b[i+j]-b[i];
}
void sort(int l, int r)
{
int i = l, j = r; long long d = b[(l+r)>>1];
for (;i <= j;)
{
for (;b[i] > d; i++);
for (;b[j] < d; j--);
if (i <= j) tmp = b[i], b[i] = b[j], b[j] = tmp, i++, j--;
}
if (i < r) sort(i, r);
if (l < j) sort(l, j);
}
int main()
{
int i, j; bool t1 = false, t2 = false;
freopen("stone.in", "r", stdin);
freopen("stone.out", "w", stdout);
scanf("%d", &n); a[0] = -oo; a[n+1] = -oo;
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum += a[i];
if (!a[i]) a[i] = -oo; else ++tot;
}
if (a[1] == -oo) t1 = true; if (a[n] == -oo) t2 = true;
for (i = 1; i <= n; i++) pred[i] = i-1, next[i] = i+1;
for (i = 1; i <= n; i++)
if (a[i] != -oo) maintain(i);
for (b[0] = -oo, i = 1, j = 0; i <= n; i=next[i])
{
if (a[i] != -oo) b[++j] = a[i];
else if (b[j] != -oo) b[++j] = -oo;
}
for (;b[j] == -oo;j--); n = j;
b[0] = -oo; b[n+1] = -oo;
if (!t1)change(1, 1);
if (!t2)change(n, -1);
sort(1, n);
for (i = 1; i <= n && b[i] != -oo; i++)
if (i & 1) ans += b[i]; else ans -= b[i];
printf("%I64d %I64d", sum+ans >> 1, sum-ans >> 1);
return 0;
}
city
......
Bounce:
題意:与えられたシーケンスk[n]、2つの操作、1つの修正操作、ある位置のkを修正し、1つの質問操作、i位置から質問し、i+k[I]にジャンプするたびに、最後に何回ジャンプしてシーケンスから飛び出すことができるかを聞く.
正解はダイナミックツリーを使いますが、結局恥知らずにチェーン水で渡りました.
kをsqrt(n)に分けて、各位置がそのブロックから飛び出すステップ数と飛び出す場所を統計して、このように各質問はsqrt(n)レベルで、速度はやっと強いです;
# include <cstdio>
# include <cstdlib>
# include <cmath>
using namespace std;
const int maxn = 300000;
int aux[maxn], k[maxn], head[maxn], tail[maxn], go[maxn], cost[maxn];
int n, m, size, num;
inline void change(int st, int d)
{
int i, id = aux[st]; k[st] = d;
for (i = st; i >= head[id]; i--)
if (i+k[i] > tail[id]) cost[i] = 1, go[i] = i+k[i];
else go[i] = go[i+k[i]], cost[i] = cost[i+k[i]]+1;
}
void prepare()
{
int i, j;
size = (int) floor(sqrt(n))+1;
for (i = 1, num = 0; i <= n; i+= size)
head[++num] = i, tail[num] = i+size-1;
tail[num] = n;
for (i = 1; i <= num; i++)
for (j = head[i]; j <= tail[i]; j++)
aux[j] = i;
for (i = 1; i <= num; i++)
change(tail[i], k[tail[i]]);
}
inline int ask(int st)
{
int ans;
for (ans = 0; st <= n; st = go[st])
ans += cost[st];
return ans;
}
int main()
{
int st, c, i, d;
freopen("bounce.in", "r", stdin);
freopen("bounce.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &k[i]);
prepare();
scanf("%d", &m);
for (i = 1; i <= m; i++)
{
scanf("%d", &c);
if (c == 1)
{
scanf("%d", &st); st++;
printf("%d
", ask(st));
}
else
{
scanf("%d%d", &st, &d); st++;
change(st, d);
}
}
return 0;
}
Matrix:
标题:与えられたb[N][N],b[I][J]=a[i][j]+a[i-1][j]+a[i][j-1]+a[i-1][j-1]辞書の順序の最小のAを求めます
Aの元素は10を超えず、n<=200である.
この問題は恥知らずに他の人のb,aと補助配列cに関する公式を写した.
Ai,j= Ci,j + (-1)^i+j-2 *A1,1 + (-1)^i-1*A1,j + (-1)^j-1*Ai,1 (i>1,j>1)
ここでc[I][J]=B[I][J]-C[I-1][J]-C[I][J-1]-C[I-1][J-1];
では、最初の行の数値を検索し、最初の列の値範囲を維持し、矛盾が発生したら枝を切ることで検索できます.
ツッコミ:公式は他人のものを写して、結局その公式の指数は意外にも間違っていて、TAT、結果はずっと調整していないで、wa、wa、wa、wa............最後に手で計算して検査してやっと公式の指数が間違っていることを発見しました=!、人のスタイルを写すのは本当にいい習慣ではない.