头像

周玥




离线:2天前


问题 请教大佬

周玥
4天前

请教大佬 思路AC代码

题目:验证公式.

内存限制: 256 Mb |时间限制: 1000 ms


题目背景

我们知道

1^2+2^2+3^2+…+n^2=(2n^3+3n^2+n)/6

还有

1^3+2^3+3^3+…+n^3=(n^4+2n^3+n^2)

这些公式的结果都是一个多项式除以一个正整数,而这些公式对任何自然数这些公式的结果都是一个多项式除以一个正整数,而这些公式对任何自然数都是成立的,说明这些多项式有特殊的性质。我们可以通过检查多项式是否永远是一个正整数的倍数来判断它是否有成为一个组合数学结论的资格。


题目描述

给定一个多项式(不含常数项)

f(x)=a[n]x^n+a[n-1]x^(n-1)+…+a[2]x^2 +a[1]x^l

以及m ,请判断对任何自然数n , f(n)是否永远可以被m整除


输入格式

第一行:两个正整数n与m ;

第二行: n个整数表示a[1],a[2],… ,a[n]。

输出格式

如果输入的多项式永远是m的倍数,输出Yes;

否则,输出No。


数据范围

对于50%的数据,1≤n≤9, 1≤m≤100,-9≤a[i]≤9 ;

对于100%的数据,1≤n≤1000,1≤m≤1000,-1, 000,000≤a[i]≤1,000,000。

-----------------------------------

样例数据:


输入:

3 6
1 3 2

输出:

Yes

说明:这就是平方和公式,注意系数是按照从小到大顺序给出的。

输入:

1 3
2

输出:

No

说明:多项式2x显然不可能永远是3的倍数。

------------------------------

请教大佬




周玥
4天前

请教思路AC代码

题目:铺设地砖
内存限制: 256 Mb时间限制: 1000 ms


题目描述
有一条道路需要铺设地砖,这条道路由n×2 个方格组成。存在两种规格的地砖,一种是 1×1 规格的,也就是恰好可以覆盖一个方格,另一种是 1×2 规格的。两种规格的砖头的数量没有限制。请计算多少种方法铺设地砖的方法。

由于方案数可能很大,输出它模 1,000,000,007的余数即可


输入格式
单个正整数:表示 n。

输出格式
单个正整数:表示方案数模 1,000,000,007的余数。

数据范围
对于30%的数据,1≤n≤15;
对于 100% 的数据,1≤n≤100000。


样例数据
输入:
2
输出:
7


请教大佬



新鲜事 原文

周玥
9天前
新春佳节,祝大家新年快乐,牛气冲天,牛转乾坤。新年新气象,在2021年再创佳绩! ------2021-02-15(年初四) --p.s:迟到的祝福送给大家。
图片


活动打卡代码 AcWing 1349. 修理牛棚

周玥
27天前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 210;

int m, s, c;
int a[N], b[N];

int main()
{
cin >> m >> s >> c;
for (int i = 0; i < c; i ++ ) cin >> a[i];
sort(a, a + c);
int res = a[c - 1] - a[0] + 1;

for (int i = 1; i < c; i ++ ) b[i] = a[i] - a[i - 1] - 1;
sort(b + 1, b + c, greater<int>());

for (int i = 1; i <= m - 1 && i < c; i ++ )
    res -= b[i];

cout << res << endl;

return 0;

}



活动打卡代码 AcWing 898. 数字三角形

周玥
27天前

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int INF = 2e9;
int f[1001][1001];
int n,a[1001][1001];
int main() {
scanf(“%d”,&n);
for(register int i=1; i<=n; i)
for(register int j=1; j<=i; j
)
scanf(“%d”,&a[i][j]);
for(register int i=n; i>=1; i–)
for(register int j=i; j>=1; j–)
f[i][j] += max(f[i+1][j] , f[i+1][j+1]) + a[i][j];
printf(“%d\n”,f[1][1]);
return 0;
}



活动打卡代码 AcWing 1348. 搭配牛奶

周玥
27天前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 5010;

int n, m;
struct Milk
{
int p, a;
bool operator< (const Milk& t) const
{
return p < t.p;
}
}milk[N];

int main()
{
cin >> n >> m;
for (int i = 0; i < m; i ++ ) cin >> milk[i].p >> milk[i].a;
sort(milk, milk + m);

int res = 0;
for (int i = 0; i < m && n; i ++ )
{
    int cur = min(n, milk[i].a);
    n -= cur;
    res += cur * milk[i].p;
}

cout << res << endl;
return 0;

}



活动打卡代码 AcWing 1391. 喧嚣摇滚乐队

周玥
27天前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 25;

int n, t, m;
int f[N][N][N];

int main()
{
cin >> n >> t >> m;
for (int i = 1; i <= n; i )
{
int v;
cin >> v;
for (int j = 1; j <= m; j
)
for (int k = 0; k <= t; k ++ )
{
f[i][j][k] = f[i - 1][j][k];
if (k >= v)
{
f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - v] + 1);
f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][t] + 1);
}
}
}
cout << f[n][m][t] << endl;

return 0;

}



活动打卡代码 AcWing 1390. 通电围栏

周玥
27天前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

define x first

define y second

using namespace std;

typedef pair[HTML_REMOVED] PII;

int n, m, p;
PII q[3];

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

int main()
{
cin >> n >> m >> p;
int s = p * m;
int b = 0;
q[1] = {p, 0}, q[2] = {n, m};
for (int i = 0; i < 3; i )
for (int j = i + 1; j < 3; j
)
b += abs(gcd(q[j].x - q[i].x, q[j].y - q[i].y));

cout << (s - b + 2) / 2 << endl;
return 0;

}



活动打卡代码 AcWing 1379. 联系

周玥
27天前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 200010, M = 1 << 13;

int A, B, n, m;
int cnt[M];
struct Data
{
int k, num;
bool operator< (const Data& t) const
{
if (k != t.k) return k > t.k;
return num < t.num;
}
string get_string()
{
string res;
for (int i = num; i; i >>= 1)
res += i % 2 + ‘0’;
res.pop_back();
reverse(res.begin(), res.end());
return res;
}
}q[N];

int main()
{
string str, line;
cin >> A >> B >> m;
while (cin >> line) str += line;
int n = str.size();
for (int i = A; i <= B; i )
for (int j = 0, x = 0; j < n; j
)
{
x = x * 2 + str[j] - ‘0’;
if (j - i >= 0) x -= str[j - i] - ‘0’ << i;
if (j >= i - 1) cnt[x + (1 << i)] ++ ;
}

for (int i = 0; i < M; i ++ )
    q[i] = {cnt[i], i};

sort(q, q + M);
for (int i = 0, k = 0; i < M && k < m; i ++, k ++ )
{
    if (!q[i].k) break;
    int j = i;
    while (j < M && q[j].k == q[i].k) j ++ ;
    cout << q[i].k << endl;
    for (int a = i, b = 0; a < j; a ++, b ++ )
    {
        cout << q[a].get_string();
        if ((b + 1) % 6 == 0) cout << endl;
        else cout << ' ';
    }
    if ((j - i) % 6) cout << endl;
    i = j - 1;
}

return 0;

}



活动打卡代码 AcWing 1140. 最短网络

周玥
27天前

include[HTML_REMOVED]

using namespace std;
const int N = 110;
const int INF = 0x3f3f3f3f;

int n;
int g[N][N], dist[N];
bool st[N];

int prime()
{
int res = 0;
memset(dist, 0x3f, sizeof dist);

for(int i = 0; i < n; i ++)
{
    int t = -1;
    for(int j = 0; j < n; j ++)
        if(!st[j] && (t == -1 || dist[t] >dist[j]))
            t = j;

    if(i) res += dist[t];
    for(int j = 0; j < n; j ++)     
        dist[j] = min(dist[j], g[t][j]);
    st[t] = true;
}
return res;

}

int main()
{
cin >> n;
for(int i = 0; i < n; i )
for(int j = 0; j < n; j
)
cin >> g[i][j];

cout << prime() << endl;

return 0;

}