第3回選抜試合.
3704 ワード
まず口砲AC一波、暇を見つけてから補題2333~~~
Aネットワークストリーム、理論はAC...
B構想:個数を統計し、check c h e c kする.主にコードを書く工夫で、バカな1 Aを犯さなくても大丈夫です.
C考え方:クラシックなBFSコースです.コードを書くときはtrickに気をつけてください.
D構想:マトリクス高速べき乗.このテーマには卵が痛いtrickがあります.まずデータが爆発するかどうかをチェックする必要があります.爆発したらきっと解けません.逆に解があるかもしれません.
解法1:2つの項に基づいて、2回の行列の高速べき乗を走って初項を求め、それから方程式を解いてもう一度行列の高速べき乗を走る.解法2:小さい項を第1項とし,k kの大きさに応じて前から後へ押すか,後ろから前へ押すかを選択する.弟の不思議な考えは、逆さまに行列を作って速くべき乗する.
E構想:P−L P−Lの因子をスクリーニングする.
F構想:各位置の全体への寄与を考慮すると,その後配列の組合せに類似している.ここでは参考にコードをあげます.
G構想:f[i]f[i]をi番目のi項誤り式とする.結果はCkm∗Σn−mi=0 f[m−k+i]∗Cin−mCm−k∗Σi=0 n−mf[m−k+i]∗Cn−miであった.
H解法一:BFS B F Sはブロックを一度に接続して、それからcheck c h e c k.解法2:そしてセットを調べてすべてのサブツリーを求めて、それからcheck c h e c k.
I考え方:線分木で作る.最大1429431 1429431までであり、最初のシーケンスが奇数であるため、奇数を1に置く.その後、すべてのlucky numberを前処理し、非lucky numberを0に設定し、セグメントツリーが区間のlucky number総数を維持します.n番目のlucky numberについては,簡単に求めることができる.
Aネットワークストリーム、理論はAC...
B構想:個数を統計し、check c h e c kする.主にコードを書く工夫で、バカな1 Aを犯さなくても大丈夫です.
C考え方:クラシックなBFSコースです.コードを書くときはtrickに気をつけてください.
D構想:マトリクス高速べき乗.このテーマには卵が痛いtrickがあります.まずデータが爆発するかどうかをチェックする必要があります.爆発したらきっと解けません.逆に解があるかもしれません.
解法1:2つの項に基づいて、2回の行列の高速べき乗を走って初項を求め、それから方程式を解いてもう一度行列の高速べき乗を走る.解法2:小さい項を第1項とし,k kの大きさに応じて前から後へ押すか,後ろから前へ押すかを選択する.弟の不思議な考えは、逆さまに行列を作って速くべき乗する.
E構想:P−L P−Lの因子をスクリーニングする.
F構想:各位置の全体への寄与を考慮すると,その後配列の組合せに類似している.ここでは参考にコードをあげます.
#include
#include
#include
using namespace std;
typedef long long LL;
LL f[40];
LL Work(LL n) {
LL ans = 0;
if(n >= 0) ans++;
LL m = 1;
LL yu = 0;
int num = 0;
while(n) {
if(n % 10 == 0) {
if(num == 0) {
ans += n / 10;
}
else {
ans += (n / 10 - 1) * m + yu + 1;
}
}
else {
ans += n / 10 * m;
yu = f[num] * (n % 10) + yu;
}
n /= 10; m *= 10;
num++;
}
return ans;
}
int main()
{
int i; f[0] = 1;
for(i = 1; i <= 32; i++) {
f[i] = f[i - 1] * 10;
}
int t, kcase = 1; scanf("%d", &t);
while(t--) {
LL m, n; scanf("%lld%lld", &m, &n);
printf("Case %d: %lld
", kcase++, Work(n) - Work(m - 1));
}
return 0;
}
G構想:f[i]f[i]をi番目のi項誤り式とする.結果はCkm∗Σn−mi=0 f[m−k+i]∗Cin−mCm−k∗Σi=0 n−mf[m−k+i]∗Cn−miであった.
H解法一:BFS B F Sはブロックを一度に接続して、それからcheck c h e c k.解法2:そしてセットを調べてすべてのサブツリーを求めて、それからcheck c h e c k.
I考え方:線分木で作る.最大1429431 1429431までであり、最初のシーケンスが奇数であるため、奇数を1に置く.その後、すべてのlucky numberを前処理し、非lucky numberを0に設定し、セグメントツリーが区間のlucky number総数を維持します.n番目のlucky numberについては,簡単に求めることができる.