牛客OI周赛15-普及组
A题 普通的模拟就不多说了 放个代码
#include<bits/stdc++.h>
using namespace std;
int T;
int main()
{
cin >> T;
while(T --)
{
string str;
cin >> str;
bool flag = true;
for (int i = 0; i < str.length() && flag; i = i+2){
if(str[i] == 'm' && str[i + 1] == 'q') continue;
else flag = false;
}
if(flag) puts("Yes");
else puts("No");
}
}B题
自己想的方法加上巨佬们的方法，大概有三种。
1：也是标程的方法，背包求方案数目。具体来说，就是设每个盒子是一个背包。然后dp[i][j]表示前i个背包且总和为j的方案数。
转移方程如下：
for (int i = 0; i < n; i ++) //n表示盒子的种类
for (int j = 0; j < n[i]; j ++) //n[i]表示每一个盒子内的宝物的数目
for (int s = ma; s >= a[i][j]; s --)
dp[i][s] += dp[i - 1][s - a[i][j]];
完整代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = N * N;
int n, k;
int m[N], a[N][N];
int dp[N][M];
int main()
{
cin >> n >> k;
int ma = 0;
for (int i = 1; i <= n; i ++)
{
cin >> m[i];
int cur = 0;
for (int j = 1; j <= m[i]; j ++)
{
cin >> a[i][j];
cur = max(cur, a[i][j]);
}
ma += cur;
}
dp[0][0] = 1;
for (int i = 1; i <= n; i ++) //n表示盒子的种类
for (int j = 1; j <= m[i]; j ++) //m[i]表示每一个盒子内的宝物的数目
for (int s = ma; s >= a[i][j]; s --)
if(dp[i - 1][s - a[i][j]])
dp[i][s] += dp[i - 1][s - a[i][j]];
int nu = 0, sum = 0;
for (int i = 1; i <= ma; i ++)
{
while(dp[n][i])
{
sum += i;
nu++;
dp[n][i]--;
if(nu == k) return printf("%d\n", sum), 0;
}
}
}
第二种方法：
维护一个最小堆：首先把第一个盒子内的宝石加入堆中，然后把堆中的元素从小到大取出存入另外一个数组b，与第二个盒子中的数组a进行求和，放入堆中，依次做下去即可。可以减枝的地方：因为是固定数组a的某个宝石，而且数组b是从小到大进行枚举，所以如果a[i] + b[j] >= que.top() 就可以break
代码：
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int N = 10001;
priority_queue <int> pq;
int n, m, k, o, oo;
int a[N], b[N];
int main() {
n = read(), k = read();
pq.push(0);
while (n--) {
m = read();
for (int j = 1; j <= m; j++) {
a[j] = read();
}
sort(a + 1, a + m + 1);
o = 0;
while (!pq.empty()) {
b[++o] = pq.top();
pq.pop();
}
oo = 0;
for (int i = 1; i <= m; i++) {
for (int j = o; j >= 1; j--) {
if (oo < k) oo++, pq.push(a[i] + b[j]);
else if (pq.top() <= a[i] + b[j]) break;
else pq.pop(), pq.push(a[i] + b[j]);
}
}
}
o = 0;
while (!pq.empty()) {
b[++o] = pq.top();
pq.pop();
}
ll ans = 0;
for (int i = o; i >= 1; i--) {
ans += b[i];
}
printf("%lld\n", ans);
return 0;
}方法3: 暴力fft 把每个盒子当作一个多项式，宝石的数目当作指数，100个多项式相乘，取前k项（最小的k个幂次）的系数和即可。
代码暂时不会写。（留坑）
C题：
标程的做法没理解精髓，暂时先不写。
D题：
两元应该都会把。
三元的话，开两个树状数组，一个维护比某个数a[i]先出现并且比他小的数的个数n1。另外一个维护比他后出现且比他大的数的个数n2。这样对于这个数a[i]对答案的贡献就是n1 * n2。但这样做不好拓展，之前是算每个值得贡献（用比他小的个数 * 比他大的个数），我们换一个思路，也是开两个树状数组，第一个同样维护比某个数a[i]先出现并且比他小的数的个数n1，与此同时把第一个树状数组的区间（1，a[i]-1)的和sum 加到第二个树状数组的a[i]所对应的位置。什么意思呢？其实就是二元逆序对的逆序对个数。把第一个逆序对看成一个整体也就是把一对逆序对看成一个数。而第二个树状数组就是去算出每个a[i]之前有几对逆序对，这样就和二元一样了。
拓展到n元的话，就开n个树状数组就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxn = 1e5+5;
int a[maxn],b[maxn];
ll sum[maxn][55];
void update(int x,int y,int n,int k)
{
while(x<=n)
{
sum[x][y]+=k;
sum[x][y]%=mod;
x+=x&-x;
}
}
ll query(int x,int y)
{
if(y==0)return 1ll*1;
ll ans = 0;
while(x)
{
ans+=sum[x][y];
x-=x&-x;
ans%=mod;
}
return ans;
}
int main()
{
int n,k;
scanf("%d%d", &n, &k);
for(int i = 1;i <= n; ++i)
scanf("%d",&a[i]),b[i] = a[i];
sort(b + 1,b + 1 + n);
int m = unique(b + 1,b + 1 + n) - b - 1;
for(int i = 1;i <= n;++i)
a[i] = lower_bound(b + 1,b + 1 + m, a[i]) - b;
ll ans = 0;
for(int i = 1;i <= n;++i)
{
for(int j = 1; j <= k; ++j)
{
ll p = query(a[i] - 1, j - 1);
if(j == k)ans+=p,ans%=mod;
update(a[i], j, n, p);
}
}
cout << ans << endl;
return 0;
}
投递58到家等公司10个岗位 >
