第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構想:各位置の全体への寄与を考慮すると,その後配列の組合せに類似している.ここでは参考にコードをあげます.
#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については,簡単に求めることができる.