2019icpc徐州站 Cat 计蒜客 - 42540 && The Answer to the Ultimate Question of Life, The Universe, and Everything. 计蒜客

VJ链接：https://vjudge.net/contest/412095#problem/A

Cat 计蒜客 - 42540

题意：

给你一个区间[L,R]，给你现在拥有的钱S。你需要从[L,R]区间中选取一些连续的数，如果i^(i+1)^(i+2)^...^(j-1)^j<=s（L<=i<=j<=R）,那么你就可以拥有[i,j]这一个子区间。问你你拥有的子区间长度最长是多少

1<=L,R<=1e18

1<=S<=2e18

题解：

你会发现4k^(4k+1)^(4k+2)^(4k+3)==0（k取正整数）

那么对于一个给定的区间[L,R]，如果R-L<=4我们暴力找i，j就可以

否则我们可以把这个区间中间的4个数为一组都变成0，那么最坏情况下数组就是

{4k+1,4k+2,4k+3,(中间都是0不用管),4L,4L+1,4L+2}

那么我们只需要暴力枚举数组{4k+1,4k+2,4k+3,4L,4L+1,4L+2}就可以

代码：

#include <bits/stdc++.h>

typedef long long ll;

ll max(ll a, ll b)

{

    if (a > b)

        return a;

    else

        return b;

}

ll que[100];

int main()

{

    ll t;

    scanf("%lld", &t);

    while (t--)

    {

        ll L, R, s;

        scanf("%lld%lld%lld", &L, &R, &s);

        if (R - L + 1 <= 4)

        {

            ll res = 0;

            for (ll i = L; i <= R; ++i)

            {

                ll now = i;

                if (s >= now)

                    res = max(res, 1);

                for (ll j = i + 1; j <= R; ++j)

                {

                    now ^= j;

                    if (s >= now)

                        res = max(res, j - i + 1);

                }

            }

            if (res == 0)

                res = -1;

            printf("%lld\n", res);

        }

        else

        {

            ll len = 0, a = 0, b = 0;

            if ((L % 4) != 0)

            {

                a = (L / 4 + 1) * 4;

                for (ll i = L; i < (L / 4 + 1) * 4; ++i)

                {

                    que[++len] = i;

                }

            }

            else

                a = L;

            if ((R + 1) % 4 != 0)

            {

                b = (R / 4) * 4 - 1;

                for (ll i = (R / 4) * 4; i <= R; ++i)

                {

                    que[++len] = i;

                }

            }

            else

                b = R;

            ll res = 0;

            for (ll i = 1; i <= len; ++i)

            {

                ll now = que[i];

                if (s >= now)

                    res = max(res, 1);

                for (ll j = i + 1; j <= len; ++j)

                {

                    now ^= que[j];

                    if (s >= now)

                    {

                        // if (j - i + 1 == 4)

                        //     printf("%lld %lld %lld\n", now, i, j);

                        res = max(res, j - i + 1);

                    }

                }

            }

            //printf("%lld %lld\n", b - a + 1, len);

            if (res + max(0, (b - a + 1)) == 0)

                res = -1;

            printf("%lld\n", res + max(0, (b - a + 1)));

        }

    }

    return 0;

}

/*

3

1283 23421 27681

11243 19862 25325

7061 4227 31283

*/

计蒜客 - 42545

题意：

给你一个x，为你可不可以把x=i*i*i+j*j*j+k*k*k

5000<=i,j,k<=5000

1<=x<=200

题解：

打表过的

代码太长，折叠了

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 5;

struct node

{

    int a, b, c;

} w[205];

int vis[205];

void init()

{

    vis[1] = 1, w[1].a = -5000;

    w[1].b = 1;

    w[1].c = 5000;

    vis[2] = 1, w[2].a = -4373;

    w[2].b = -486;

    w[2].c = 4375;

    vis[3] = 1, w[3].a = -5;

    w[3].b = 4;

    w[3].c = 4;

    vis[6] = 1, w[6].a = -637;

    w[6].b = -205;

    w[6].c = 644;

    vis[7] = 1, w[7].a = -169;

    w[7].b = 44;

    w[7].c = 168;

    vis[8] = 1, w[8].a = -5000;

    w[8].b = 2;

    w[8].c = 5000;

    vis[9] = 1, w[9].a = -216;

    w[9].b = -52;

    w[9].c = 217;

    vis[10] = 1, w[10].a = -650;

    w[10].b = -353;

    w[10].c = 683;

    vis[11] = 1, w[11].a = -695;

    w[11].b = -641;

    w[11].c = 843;

    vis[12] = 1, w[12].a = -11;

    w[12].b = 7;

    w[12].c = 10;

    vis[15] = 1, w[15].a = -265;

    w[15].b = -262;

    w[15].c = 332;

    vis[16] = 1, w[16].a = -4114;

    w[16].b = -588;

    w[16].c = 4118;

    vis[17] = 1, w[17].a = -3331;

    w[17].b = 2195;

    w[17].c = 2977;

    vis[18] = 1, w[18].a = -1373;

    w[18].b = -1276;

    w[18].c = 1671;

    vis[19] = 1, w[19].a = -95;

    w[19].b = 47;

    w[19].c = 91;

    vis[20] = 1, w[20].a = -2816;

    w[20].b = -741;

    w[20].c = 2833;

    vis[21] = 1, w[21].a = -401;

    w[21].b = -287;

    w[21].c = 445;

    vis[24] = 1, w[24].a = -10;

    w[24].b = 8;

    w[24].c = 8;

    vis[25] = 1, w[25].a = -2683;

    w[25].b = 1839;

    w[25].c = 2357;

    vis[26] = 1, w[26].a = -2107;

    w[26].b = 237;

    w[26].c = 2106;

    vis[27] = 1, w[27].a = -5000;

    w[27].b = 3;

    w[27].c = 5000;

    vis[28] = 1, w[28].a = -2268;

    w[28].b = -249;

    w[28].c = 2269;

    vis[29] = 1, w[29].a = -233;

    w[29].b = -69;

    w[29].c = 235;

    vis[34] = 1, w[34].a = -1555;

    w[34].b = -244;

    w[34].c = 1557;

    vis[35] = 1, w[35].a = -1120;

    w[35].b = -509;

    w[35].c = 1154;

    vis[36] = 1, w[36].a = -3223;

    w[36].b = 2358;

    w[36].c = 2731;

    vis[37] = 1, w[37].a = -444;

    w[37].b = -84;

    w[37].c = 445;

    vis[38] = 1, w[38].a = -27;

    w[38].b = 16;

    w[38].c = 25;

    vis[43] = 1, w[43].a = -823;

    w[43].b = -307;

    w[43].c = 837;

    vis[44] = 1, w[44].a = -7;

    w[44].b = -5;

    w[44].c = 8;

    vis[45] = 1, w[45].a = -2369;

    w[45].b = 1709;

    w[45].c = 2025;

    vis[46] = 1, w[46].a = -758;

    w[46].b = -473;

    w[46].c = 815;

    vis[47] = 1, w[47].a = -141;

    w[47].b = 49;

    w[47].c = 139;

    vis[48] = 1, w[48].a = -3950;

    w[48].b = -1247;

    w[48].c = 3991;

    vis[51] = 1, w[51].a = -796;

    w[51].b = 602;

    w[51].c = 659;

    vis[53] = 1, w[53].a = -2370;

    w[53].b = 1518;

    w[53].c = 2141;

    vis[54] = 1, w[54].a = -3885;

    w[54].b = -648;

    w[54].c = 3891;

    vis[55] = 1, w[55].a = -3329;

    w[55].b = 1837;

    w[55].c = 3131;

    vis[56] = 1, w[56].a = -672;

    w[56].b = 505;

    w[56].c = 559;

    vis[57] = 1, w[57].a = -998;

    w[57].b = 361;

    w[57].c = 982;

    vis[60] = 1, w[60].a = -1201;

    w[60].b = -163;

    w[60].c = 1202;

    vis[61] = 1, w[61].a = -966;

    w[61].b = 668;

    w[61].c = 845;

    vis[62] = 1, w[62].a = -2744;

    w[62].b = -1561;

    w[62].c = 2903;

    vis[63] = 1, w[63].a = -161;

    w[63].b = 102;

    w[63].c = 146;

    vis[64] = 1, w[64].a = -5000;

    w[64].b = 4;

    w[64].c = 5000;

    vis[65] = 1, w[65].a = -929;

    w[65].b = 403;

    w[65].c = 903;

    vis[66] = 1, w[66].a = 1;

    w[66].b = 1;

    w[66].c = 4;

    vis[69] = 1, w[69].a = -403;

    w[69].b = 134;

    w[69].c = 398;

    vis[70] = 1, w[70].a = -2359;

    w[70].b = 824;

    w[70].c = 2325;

    vis[71] = 1, w[71].a = -533;

    w[71].b = 401;

    w[71].c = 443;

    vis[72] = 1, w[72].a = -432;

    w[72].b = -104;

    w[72].c = 434;

    vis[73] = 1, w[73].a = -335;

    w[73].b = -146;

    w[73].c = 344;

    vis[78] = 1, w[78].a = -2080;

    w[78].b = -829;

    w[78].c = 2123;

    vis[79] = 1, w[79].a = -706;

    w[79].b = -196;

    w[79].c = 711;

    vis[80] = 1, w[80].a = -1300;

    w[80].b = -706;

    w[80].c = 1366;

    vis[81] = 1, w[81].a = -2368;

    w[81].b = -1719;

    w[81].c = 2638;

    vis[82] = 1, w[82].a = -1317;

    w[82].b = 847;

    w[82].c = 1188;

    vis[83] = 1, w[83].a = -3707;

    w[83].b = 1315;

    w[83].c = 3651;

    vis[87] = 1, w[87].a = -4126;

    w[87].b = -1972;

    w[87].c = 4271;

    vis[88] = 1, w[88].a = -1390;

    w[88].b = -1282;

    w[88].c = 1686;

    vis[89] = 1, w[89].a = -2514;

    w[89].b = 1953;

    w[89].c = 2036;

    vis[90] = 1, w[90].a = -1803;

    w[90].b = 365;

    w[90].c = 1798;

    vis[91] = 1, w[91].a = -3389;

    w[91].b = -2912;

    w[91].c = 3992;

    vis[92] = 1, w[92].a = -4052;

    w[92].b = 861;

    w[92].c = 4039;

    vis[93] = 1, w[93].a = -248;

    w[93].b = -98;

    w[93].c = 253;

    vis[96] = 1, w[96].a = -22;

    w[96].b = 14;

    w[96].c = 20;

    vis[97] = 1, w[97].a = -3168;

    w[97].b = -991;

    w[97].c = 3200;

    vis[98] = 1, w[98].a = -2101;

    w[98].b = -1638;

    w[98].c = 2391;

    vis[99] = 1, w[99].a = -893;

    w[99].b = -622;

    w[99].c = 984;

    vis[100] = 1, w[100].a = -1797;

    w[100].b = -903;

    w[100].c = 1870;

    vis[101] = 1, w[101].a = -2327;

    w[101].b = 319;

    w[101].c = 2325;

    vis[102] = 1, w[102].a = -239;

    w[102].b = 118;

    w[102].c = 229;

    vis[105] = 1, w[105].a = -7;

    w[105].b = -4;

    w[105].c = 8;

    vis[106] = 1, w[106].a = -2689;

    w[106].b = -1165;

    w[106].c = 2760;

    vis[107] = 1, w[107].a = -1309;

    w[107].b = 947;

    w[107].c = 1117;

    vis[108] = 1, w[108].a = -1165;

    w[108].b = -948;

    w[108].c = 1345;

    vis[109] = 1, w[109].a = -2948;

    w[109].b = 853;

    w[109].c = 2924;

    vis[111] = 1, w[111].a = -4793;

    w[111].b = -2312;

    w[111].c = 4966;

    vis[115] = 1, w[115].a = -12;

    w[115].b = 8;

    w[115].c = 11;

    vis[116] = 1, w[116].a = -1906;

    w[116].b = -757;

    w[116].c = 1945;

    vis[117] = 1, w[117].a = -896;

    w[117].b = -555;

    w[117].c = 962;

    vis[118] = 1, w[118].a = -4328;

    w[118].b = 383;

    w[118].c = 4327;

    vis[119] = 1, w[119].a = -3677;

    w[119].b = -1673;

    w[119].c = 3789;

    vis[120] = 1, w[120].a = -2804;

    w[120].b = 1219;

    w[120].c = 2725;

    vis[123] = 1, w[123].a = -37;

    w[123].b = -16;

    w[123].c = 38;

    vis[124] = 1, w[124].a = -1;

    w[124].b = 0;

    w[124].c = 5;

    vis[125] = 1, w[125].a = -5000;

    w[125].b = 5;

    w[125].c = 5000;

    vis[126] = 1, w[126].a = -2212;

    w[126].b = -419;

    w[126].c = 2217;

    vis[127] = 1, w[127].a = -4034;

    w[127].b = -3881;

    w[127].c = 4988;

    vis[128] = 1, w[128].a = -3989;

    w[128].b = -726;

    w[128].c = 3997;

    vis[129] = 1, w[129].a = -1580;

    w[129].b = -1238;

    w[129].c = 1801;

    vis[132] = 1, w[132].a = -1;

    w[132].b = 2;

    w[132].c = 5;

    vis[133] = 1, w[133].a = -399;

    w[133].b = 167;

    w[133].c = 389;

    vis[134] = 1, w[134].a = -3013;

    w[134].b = -1766;

    w[134].c = 3203;

    vis[135] = 1, w[135].a = -1351;

    w[135].b = -629;

    w[135].c = 1395;

    vis[136] = 1, w[136].a = -1116;

    w[136].b = 816;

    w[136].c = 946;

    vis[137] = 1, w[137].a = -758;

    w[137].b = -428;

    w[137].c = 801;

    vis[138] = 1, w[138].a = -86;

    w[138].b = -77;

    w[138].c = 103;

    vis[141] = 1, w[141].a = -139;

    w[141].b = 104;

    w[141].c = 116;

    vis[142] = 1, w[142].a = -7;

    w[142].b = -3;

    w[142].c = 8;

    vis[144] = 1, w[144].a = -2746;

    w[144].b = -2552;

    w[144].c = 3342;

    vis[145] = 1, w[145].a = -8;

    w[145].b = -7;

    w[145].c = 10;

    vis[146] = 1, w[146].a = -327;

    w[146].b = -263;

    w[146].c = 376;

    vis[147] = 1, w[147].a = -2366;

    w[147].b = 1528;

    w[147].c = 2131;

    vis[150] = 1, w[150].a = -367;

    w[150].b = 260;

    w[150].c = 317;

    vis[151] = 1, w[151].a = -463;

    w[151].b = 215;

    w[151].c = 447;

    vis[152] = 1, w[152].a = -805;

    w[152].b = 486;

    w[152].c = 741;

    vis[153] = 1, w[153].a = -3736;

    w[153].b = -695;

    w[153].c = 3744;

    vis[154] = 1, w[154].a = -2135;

    w[154].b = -516;

    w[154].c = 2145;

    vis[155] = 1, w[155].a = -3693;

    w[155].b = -1049;

    w[155].c = 3721;

    vis[159] = 1, w[159].a = -1534;

    w[159].b = 383;

    w[159].c = 1526;

    vis[160] = 1, w[160].a = -3874;

    w[160].b = -1654;

    w[160].c = 3972;

    vis[161] = 1, w[161].a = -4767;

    w[161].b = -2476;

    w[161].c = 4980;

    vis[162] = 1, w[162].a = -4125;

    w[162].b = -1417;

    w[162].c = 4180;

    vis[163] = 1, w[163].a = -3423;

    w[163].b = -2943;

    w[163].c = 4033;

    vis[164] = 1, w[164].a = -66;

    w[164].b = -59;

    w[164].c = 79;

    vis[168] = 1, w[168].a = -802;

    w[168].b = -574;

    w[168].c = 890;

    vis[169] = 1, w[169].a = -1354;

    w[169].b = -1012;

    w[169].c = 1521;

    vis[170] = 1, w[170].a = -3834;

    w[170].b = -2149;

    w[170].c = 4047;

    vis[171] = 1, w[171].a = -1328;

    w[171].b = 891;

    w[171].c = 1178;

    vis[174] = 1, w[174].a = -335;

    w[174].b = -170;

    w[174].c = 349;

    vis[177] = 1, w[177].a = -1168;

    w[177].b = -160;

    w[177].c = 1169;

    vis[178] = 1, w[178].a = -13;

    w[178].b = -10;

    w[178].c = 15;

    vis[179] = 1, w[179].a = -2839;

    w[179].b = 1503;

    w[179].c = 2691;

    vis[181] = 1, w[181].a = -4874;

    w[181].b = 974;

    w[181].c = 4861;

    vis[182] = 1, w[182].a = -90;

    w[182].b = -29;

    w[182].c = 91;

    vis[183] = 1, w[183].a = -4889;

    w[183].b = 976;

    w[183].c = 4876;

    vis[186] = 1, w[186].a = -4;

    w[186].b = 5;

    w[186].c = 5;

    vis[187] = 1, w[187].a = -1885;

    w[187].b = -1092;

    w[187].c = 2000;

    vis[188] = 1, w[188].a = -1639;

    w[188].b = 318;

    w[188].c = 1635;

    vis[189] = 1, w[189].a = -1702;

    w[189].b = -1403;

    w[189].c = 1974;

    vis[190] = 1, w[190].a = -4812;

    w[190].b = -593;

    w[190].c = 4815;

    vis[191] = 1, w[191].a = -377;

    w[191].b = -215;

    w[191].c = 399;

    vis[192] = 1, w[192].a = -20;

    w[192].b = 16;

    w[192].c = 16;

    vis[196] = 1, w[196].a = -1057;

    w[196].b = -579;

    w[196].c = 1112;

    vis[197] = 1, w[197].a = -2867;

    w[197].b = -1606;

    w[197].c = 3026;

    vis[198] = 1, w[198].a = -3752;

    w[198].b = -1347;

    w[198].c = 3809;

    vis[199] = 1, w[199].a = -2208;

    w[199].b = 508;

    w[199].c = 2199;

    vis[200] = 1, w[200].a = -2318;

    w[200].b = -638;

    w[200].c = 2334;

}

int main()

{

    init();

    int t;

    scanf("%d", &t);

    while (t--)

    {

        int n;

        scanf("%d", &n);

        if (n == 0)

        {

            puts("0 0 0");

            continue;

        }

        if (vis[n])

        {

            printf("%d %d %d\n", w[n].a, w[n].b, w[n].c);

        }

        else

        {

            puts("impossible");

        }

    }

    return 0;

}

/*

1 -5000 1 5000

8 -5000 2 5000

27 -5000 3 5000

64 -5000 4 5000

125 -5000 5 5000

183 -4889 976 4876

181 -4874 974 4861

190 -4812 -593 4815

111 -4793 -2312 4966

161 -4767 -2476 4980

2 -4373 -486 4375

118 -4328 383 4327

87 -4126 -1972 4271

162 -4125 -1417 4180

16 -4114 -588 4118

92 -4052 861 4039

127 -4034 -3881 4988

128 -3989 -726 3997

48 -3950 -1247 3991

54 -3885 -648 3891

160 -3874 -1654 3972

170 -3834 -2149 4047

198 -3752 -1347 3809

153 -3736 -695 3744

83 -3707 1315 3651

155 -3693 -1049 3721

119 -3677 -1673 3789

163 -3423 -2943 4033

91 -3389 -2912 3992

17 -3331 2195 2977

55 -3329 1837 3131

36 -3223 2358 2731

97 -3168 -991 3200

134 -3013 -1766 3203

109 -2948 853 2924

197 -2867 -1606 3026

179 -2839 1503 2691

20 -2816 -741 2833

120 -2804 1219 2725

144 -2746 -2552 3342

62 -2744 -1561 2903

106 -2689 -1165 2760

25 -2683 1839 2357

89 -2514 1953 2036

53 -2370 1518 2141

45 -2369 1709 2025

81 -2368 -1719 2638

147 -2366 1528 2131

70 -2359 824 2325

101 -2327 319 2325

200 -2318 -638 2334

28 -2268 -249 2269

126 -2212 -419 2217

199 -2208 508 2199

154 -2135 -516 2145

26 -2107 237 2106

98 -2101 -1638 2391

78 -2080 -829 2123

116 -1906 -757 1945

187 -1885 -1092 2000

90 -1803 365 1798

100 -1797 -903 1870

189 -1702 -1403 1974

188 -1639 318 1635

129 -1580 -1238 1801

34 -1555 -244 1557

159 -1534 383 1526

88 -1390 -1282 1686

18 -1373 -1276 1671

169 -1354 -1012 1521

135 -1351 -629 1395

171 -1328 891 1178

82 -1317 847 1188

107 -1309 947 1117

80 -1300 -706 1366

60 -1201 -163 1202

177 -1168 -160 1169

108 -1165 -948 1345

35 -1120 -509 1154

136 -1116 816 946

196 -1057 -579 1112

57 -998 361 982

61 -966 668 845

65 -929 403 903

117 -896 -555 962

99 -893 -622 984

43 -823 -307 837

152 -805 486 741

168 -802 -574 890

51 -796 602 659

46 -758 -473 815

137 -758 -428 801

79 -706 -196 711

11 -695 -641 843

56 -672 505 559

10 -650 -353 683

6 -637 -205 644

71 -533 401 443

151 -463 215 447

37 -444 -84 445

72 -432 -104 434

69 -403 134 398

21 -401 -287 445

133 -399 167 389

191 -377 -215 399

150 -367 260 317

174 -335 -170 349

73 -335 -146 344

146 -327 -263 376

15 -265 -262 332

93 -248 -98 253

102 -239 118 229

29 -233 -69 235

9 -216 -52 217

7 -169 44 168

63 -161 102 146

47 -141 49 139

141 -139 104 116

19 -95 47 91

182 -90 -29 91

138 -86 -77 103

164 -66 -59 79

123 -37 -16 38

38 -27 16 25

96 -22 14 20

192 -20 16 16

178 -13 -10 15

115 -12 8 11

12 -11 7 10

24 -10 8 8

145 -8 -7 10

44 -7 -5 8

105 -7 -4 8

142 -7 -3 8

186 -4 5 5

124 -1 0 5

132 -1 2 5

3 -5 4 4

66 1 1 4

147 -2366 1528 2131

190 -4812 -593 4815

4 -1

5 -1

13 -1

14 -1

22 -1

23 -1

30 -1

31 -1

32 -1

33 -1

39 -1

40 -1

41 -1

42 -1

49 -1

50 -1

52 -1

58 -1

59 -1

67 -1

68 -1

74 -1

75 -1

76 -1

77 -1

84 -1

85 -1

86 -1

94 -1

95 -1

103 -1

104 -1

110 -1

112 -1

113 -1

114 -1

121 -1

122 -1

130 -1

131 -1

139 -1

140 -1

143 -1

148 -1

149 -1

156 -1

157 -1

158 -1

165 -1

166 -1

167 -1

172 -1

173 -1

175 -1

176 -1

180 -1

184 -1

185 -1

193 -1

194 -1

195 -1

*/

巴特西

2019icpc徐州站 Cat 计蒜客 - 42540 && The Answer to the Ultimate Question of Life, The Universe, and Everything. 计蒜客 - 42545

Cat 计蒜客 - 42540

最新文章

热门文章