文章目录

• 填空题
• • 方程整数解
  • 星系炸弹
  • 奇妙的数字
  • 格子中的输出
  • 九数组分数
  • 牌型种数
  • 手链样式
• 编程题
• • 饮料换购
  • 垒骰子
  • 灾后重建

填空题

方程整数解

正确答案:

10 18 24

#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int t = sqrt(n); int ok = 0;
        for(int a = 1; a <= t; a++)
        {
            for(int b = a; b <= t; b++)
            {
                int c = n - a*a - b*b;
                c = sqrt(c);
                if(a*a + b*b + c*c == n && c >= b && b >= a)
                    printf("%d %d %d\n",a,b,c), ok = 1;
            }
        }
        if(!ok) puts("No Solution");
    }
    return 0;
}

---

星系炸弹

正确答案:

2017-08-05

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int months[13];
void init()
{
    for(int i = 1; i <= 12; i++)
    {
        if(i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 12) months[i] = 31;
        else if(i == 2) months[2] = 0;
        else months[i] = 30;
    }
}
bool inbound(int x)
{
    if((x%4 == 0 && x%100) || x%400 == 0) return true;
    return false;
}
 
int main()
{
    init();
    int year,month,day,n;
    while(~scanf("%d %d %d %d", &year,&month,&day,&n))
    {
        if(inbound(year)) months[2] = 29;
        else months[2] = 28;
        if(months[month] - day >= n)
            printf("%d-%02d-%02d\n",year,month,day+n);
        else
        {
            int t = months[month] - day;
            n -= t;
            day = 0;
            month++;
            if(month > 12) year++,month = 1;
            while(n > 0)
            {
                if(inbound(year)) months[2] = 29;
                else months[2] = 28;
                for(int i = month; i <= 12; i++)
                    for(int j = 1; j<= months[i] && n > 0; j++)
                    {
                        n--;
                        if(n == 0)
                        {
                            day = j;
                            month = i;
                            break;
                        }
                    }
                    if(n>0) year++,month = 1;
                }
                printf("%d-%02d-%02d\n",year,month,day);
            }
        }
    return 0;
}

---

奇妙的数字

正确答案:

69

#include <iostream>
#include <cstring>
using namespace std;
int a[10];
void work(long long x)
{
    while(x > 0)
    {
        a[x%10]++;
        x /= 10;
    }
}
int main()
{
    bool ok = true;

    long long ans =0;
    for(long long i = 1; i < 9876543211 && ok; i++)
    {
        memset(a,0,sizeof a);
        long long x = i*i, y = i*i*i;
        work(x); work(y);
        if(a[0] == 1 && a[1] == 1 && a[2] == 1 &&
            a[3] == 1 && a[4] == 1 && a[5] == 1 &&
            a[6] == 1 && a[7] == 1 && a[8] == 1 &&
            a[9] == 1) ok = false, ans = i;
    }
    cout<<ans<<endl;
    return 0;
}

---

格子中的输出

正确答案:

(width-strlen(buf)-2)/2,"",buf,(width-strlen(buf)-2)/2,""

#include <bits/stdc++.h>
using namespace std;
void StringInGird(int width, int height,const char* s)
{
    int i,k;
    char buf[1000];
    strcpy(buf, s);
    if(strlen(s) > width - 2) buf[width - 2] = 0;
    printf("+");
    for(int i = 0; i < width - 2; i++) printf("-");
    printf("+\n");

    for(k = 1; k <(height - 1)/2; k++){
        printf("|");
        for(i = 0; i < width - 2; i++) printf(" ");
        printf("|\n");
    }
    printf("|");
    //*s 输出宽度 真实输出的内容
    printf("%*s%s%*s",(width-strlen(buf)-2)/2,"",buf,(width-strlen(buf)-2)/2,"");  //填代码

    printf("|\n");
    for(k = (height - 1)/2 + 1; k < height - 1; k++)
    {
        printf("|");
        for(i = 0; i < width - 2; i++) printf(" ");
        printf("|\n");
    }
    printf("+");
    for(i = 0; i < width - 2; i++) printf("-");
    printf("+\n");
}
int main()
{
    StringInGird(20,6,"abcd1234");
    return 0;
}

---

九数组分数

正确答案:

{ t = x[k];x[k] = x[i];x[i] = t; }

#include <bits/stdc++.h>
using namespace std;
void test(int x[])
{
    int a = x[0]*1000 + x[0]*100 + x[2]*10 + x[3];
    int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
    if(a*3 == b) printf("%d / %d\n",a,b);
}
void f(int x[], int k)
{
    int i,t;
    if(k >= 9)  //形成一个排列
    {
        test(x);  //检查
        return;
    }
    for(i = k; i < 9; i++){
        {
            t = x[k]; x[k] = x[i]; x[i] = t;  //交换，确定这一位
            f(x, k + 1);
            //填代码
            { t = x[k];x[k] = x[i];x[i] = t; } //回溯，恢复到下探之前的状态
        }
    }
}
int main()
{
    int x[] = {1,2,3,4,5,6,7,8,9};
    f(x,0);
    return 0;
}

---

牌型种数

正确答案:

3598180

#include <bits/stdc++.h>
using namespace std;
void dfs(int s,int num,int &x)
{
    if(s > 12 || num >= 13)
    {
        if(num == 13) x++;
        return;
    }
    for(int i = 0; i <= 4; i++)
    {
        num += i;
        dfs(s+1,num,x);
        num -= i;
    }
}
int main()
{
    int ans = 0;
    dfs(0,0,ans);
    cout<<ans<<endl;
    return 0;
}

---

手链样式

正确答案:

1170

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s = "000111122222";
    int ans = 0;
    vector<string>v;
    do{
        int ok = 0;
        for(auto i : v)
            if(i.find(s)!=string::npos) ok = 1;
        if(ok) continue;
        string s1 = s + s;
        v.push_back(s1);
        reverse(s1.begin(),s1.end());
        v.push_back(s1);
        ans++;
    }while(next_permutation(s.begin(),s.end()));
    cout<<ans<<endl;
    return 0;
}

---

编程题

饮料换购

题目大意
乐羊羊饮料厂正在举办一次促销优惠活动。
乐羊羊 C C C 型饮料，凭 3 个瓶盖可以再换一瓶 C C C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下，如果小明不浪费瓶盖，尽量地参加活动。
那么，对于他初始买入的n瓶饮料，最后他一共能喝到多少瓶饮料。
输入格式
输入一个整数 n n n (0 < n n n < 10000),表示初始买入的饮料数量。
输出格式
输出一个整数，表示一共能够喝到的饮料数量。
输入样例

100

输出样例

149

#include <iostream>
using namespace std;
int main()
{
    int n,cnt=0;
    while(cin>>n)
    {
        cnt=n;
        while(n>=3)
        {
            int t=n%3;
            cnt+=n/3;
            n/=3;
            n+=t;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

---

垒骰子

题目大意
赌圣 a t m atm atm 晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察， a t m atm atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
假设有 m m m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
a t m atm atm 想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 1 0 9 + 7 10^9+7 109+7 的结果。
输入格式
第一行包含两个整数 n n n, m m m，分别表示骰子的数目和排斥的组数。
接下来 m m m 行，每行两个整数 a a a, b b b，表示 a a a 和 b b b 数字不能紧贴在一起。
输出格式
共一个数，表示答案模 1 0 9 + 7 10^9+7 109+7 的结果。
输入样例

2 1
1 2

输出样例

544

/***
f[i][j]表示考虑前i个骰子，且第i个骰子上面是点数j时的方案数。
f[i][j] = f[i-1][1] + f[i-1][2] +f[i-1][3] + f[i-1][4] + f[i-1][5] + f[i-1][6]
A^(n - 1)*[4 4 4 4 4 4] = [f[n][1] f[n][2] f[n][3] f[n][4] f[n][5] f[n][6]];（列向量）
***/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
const int mod = 1e9 + 7, N = 7;
using namespace std;
typedef long long ll;

struct Matrix{
  ll m[N][N];
};

int Turn(int x)  // 转换函数
{
    if(x > 3) return x - 3;
    return x + 3;
}

Matrix mul(Matrix a, Matrix b) //矩阵乘法
{
    Matrix ans;
    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++) ans.m[i][j] = 0;

    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++)
            for(int k = 1; k < N; k++)
                ans.m[i][j] = (ans.m[i][j] + (a.m[i][k]*b.m[k][j])%mod)%mod;
    return ans;
}

ll ksm(int b,Matrix a)
{
    Matrix ans;
    for(int i = 1; i < N; i++) 
    {
        for(int j = 1; j < N; j++)
            if(!(i-1)) ans.m[i][j] = 4;   // m[1]
            else ans.m[i][j] = 0;
    }
    while(b)  //类似快速幂
    {
        if(b&1) ans = mul(ans,a);  //ans = ans*a;
        a = mul(a,a);   // a = a*a;
        b >>= 1;
    }
    ll res = 0;
    for(int i = 1; i < N; i++) res = (res + ans.m[1][i]%mod)%mod;
    return res;
}

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);

    Matrix a;
    for(int i = 1; i < N; i++)
        for(int j = 1; j < N; j++) a.m[i][j] = 4;
    while(m--)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        a.m[x][Turn(y)] = 0;
        a.m[y][Turn(x)] = 0;
    }
    
    ll ans = ksm(n - 1,a);
    printf("%lld\n",ans);
    return 0;
}

---

灾后重建

题目大意
P e a r Pear Pear 市一共有 N N N 个居民点，居民点之间有 M M M 条双向道路相连。
这些居民点两两之间都可以通过双向道路到达。
这种情况一直持续到最近，一次严重的地震毁坏了全部 M M M 条道路。
震后， P e a r Pear Pear 打算修复其中一些道路，修理第 i i i 条道路需要 P i P_i Pi​ 的时间。
不过， P e a r Pear Pear 并不打算让全部的点连通，而是选择一些标号特殊的点让他们连通。
P e a r Pear Pear 有 Q Q Q 次询问，每次询问，他会选择所有编号在 [ l , r ] [l,r] [l,r] 之间，并且 编号 m o d mod mod K K K = C C C 的点，修理一些路使得它们连通。
由于所有道路的修理可以同时开工，所以完成修理的时间取决于花费时间最长的一条路，即涉及到的道路中 i _i i​ 的最大值。
你能帮助 P e a r Pear Pear 计算出每次询问时需要花费的最少时间么？
这里询问是独立的，也就是上一个询问里的修理计划并没有付诸行动。
输入格式
第一行三个正整数 N N N、 M M M、 Q Q Q，含义如题面所述。
接下来 M M M 行，每行三个正整数 X i X_i Xi​、 Y i Y_i Yi​、 P i P_i Pi​，表示一条连接 X i X_i Xi​ 和 Y i Y_i Yi​ 的双向道路，修复需要 P i P_i Pi​ 的时间，可能有自环，可能有重边。
接下来 Q Q Q 行，每行四个正整数 L i L_i Li​、 R i R_i Ri​、 K i K_i Ki​、 C i C_i Ci​，表示这次询问的点是 [ L i , R i ] [L_i,R_i] [Li​,Ri​] 区间中所有编号 M o d Mod Mod K i K_i Ki​ = C i C_i Ci​ 的点。
保证参与询问的点至少有两个。
点的编号从 1 到 N N N。
输出格式
输出 Q Q Q 行，每行一个正整数表示对应询问的答案。
输入样例

7 10 4
1 3 10
2 6 9
4 1 5
3 7 4
3 6 9
1 5 8
2 7 4
3 2 10
1 7 6
7 6 9
1 7 1 0
1 7 3 1
2 5 1 0
3 7 2 1

输出样例

9
6
8
8