A：做游戏
思路：牛牛贪心选择即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c, x, y, z;
int main(){
while(scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &x, &y, &z) != EOF){
ll ans = 0;
ans += min(a, y);
ans += min(b, z);
ans += min(c, x);
printf("%lld\n", ans);
}
return 0;
}
B：排数字
思路：由于问子串是616的最多个数，贪心地构造616，最后计算答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
char s[maxn];
int n;
int num1, num2;
int main(){
while(scanf("%d", &n) != EOF){
num1 = num2 = 0;
scanf("%s", s + 1);
for(int i = 1; i <= n; i++){
if(s[i] == '6') num1++;
if(s[i] == '1') num2++;
}
num1--;
printf("%d\n", max(min(num1, num2), 0));
}
return 0;
}
C：算概率
思路：设dp[i][j]表示前 i 道题回答出 j 题的概率
显然dp更新式子为:dp[i][j] = dp[i - 1][j] * (第 i 题未答对) + dp[i - 1][j - 1] * （第 i 题答对）
注意：此题给出的概率是模过之后的数，所以
dp[i][j] = dp[i - 1][j] * ((1 - p[i] + mod) % mod) % mod + dp[i - 1][j - 1] * p[i] % mod; dp[i][j] %= mod; 更新dp[i][0]时要注意一下，因为dp[i - 1][-1]无意义
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 2e3 + 5;
ll p[maxn];
ll dp[maxn][maxn];
int n;
int main(){
while(scanf("%d", &n) != EOF){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) scanf("%lld", &p[i]);
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] * ((1 - p[i] + mod) % mod) % mod;
for(int j = 1; j <= i; j++){
dp[i][j] = dp[i - 1][j] * ((1 - p[i] + mod) % mod) % mod + dp[i - 1][j - 1] * p[i] % mod;
dp[i][j] %= mod;
}
}
for(int i = 0; i <= n; i++){
printf("%lld%c", dp[n][i], i == n ? '\n' : ' ');
}
}
return 0;
}D:数三角
思路：考虑到n最多才500，可以接受的复杂度，所以暴力枚举3个点，判断是否是钝角三角形。判断时，要注意三点不可以共线，用向量即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 2e3 + 5;
struct P{
ll x, y;
}p[505];
int n;
bool solve(int i, int j, int k){
ll x1 = p[j].x - p[i].x;
ll y1 = p[j].y - p[i].y;
ll x2 = p[k].x - p[i].x;
ll y2 = p[k].y - p[i].y;
if(x1 * x2 + y1 * y2 < 0 && x1 * y2 != x2 * y1){
return true;
}
return false;
}
int main(){
while(scanf("%d", &n) != EOF){
for(int i = 1; i <= n; i++){
scanf("%lld%lld", &p[i].x, &p[i].y);
}
ll ans = 0;
for(int i = 1; i <= n - 2; i++){
for(int j = i + 1; j <= n - 1; j++){
for(int k = j + 1; k <= n; k++){
if(solve(i, j, k) || solve(j, i, k) || solve(k, i, j)) ans++;
}
}
}
printf("%lld\n", ans);
}
return 0;
}
E：做计数
感受：卡这题活活把我卡了2h，心态崩溃，打表打了3000多行，然后发现由于代码太长，提交不了。幸亏我卡了2h后，开了其他题，A了2题之后心态缓和，然后再看这一题，发现就是***题。还是我太菜了
思路： ，且
。两边同时平方,
我们就可以暴力枚举
然后对于每一个平方数，我们只需要求出其因数个数即可（i * j = 平方数）
这个数论问题在寒假基础训练营第一场也有裸题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
ll n;
ll Get(ll n){
ll ans = 1;
for(ll i = 2; i * i <= n; i++){
if(n % i == 0){
ll num = 1;
while(n % i == 0){
num++;
n /= i;
}
ans *= num;
}
}
if(n > 1) ans *= 2;
return ans;
}
int main(){
while(scanf("%lld", &n) != EOF){
ll ans = 0;
for(ll i = 1; i * i <= n; i++){
ans += Get(i * i);
}
printf("%lld\n", ans);
}
return 0;
}
F：拿物品
思路：刚开始看这个题目，还以为是多校原题，不过仔细想想，忘记多校那题题目是什么了。
由于两个人都是想让自己的得分，比对方的得分多得多，所以我们就把这个问题转化一下。
假设两个人现在血量均为0
并设一个物品的两个属性为，假设牛牛拿这个物品，它的血量加a, 牛可乐血量加 -b，那么问题转化为他们的血量差
那么这个问题就简化了，每一个人选择物品的原则是，尽量让自己加的血量 + 对手减的血量最大。
简单排序，选择即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
struct Node{
int pos;
ll val;
}a[maxn];
ll n;
bool cmp(Node a, Node b){
return a.val > b.val;
}
int main(){
while(scanf("%lld", &n) != EOF){
for(int i = 1; i <= n; i++) scanf("%lld", &a[i].val);
ll tmp;
for(int i = 1; i <= n; i++){
scanf("%lld", &tmp);
a[i].val += tmp;
a[i].pos = i;
}
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i += 2){
printf("%d ", a[i].pos);
}
putchar('\n');
for(int i = 2; i <= n; i += 2){
printf("%d ", a[i].pos);
}
putchar('\n');
}
return 0;
}
G：判正误
感受：这一题也卡了我好久，最后是看有1000人过了才想到用极端方法跑的。主要是一开始看到这题，想到的是以前做过的题目，好像是一个结论题，想了挺久。
思路：直接取几个质数暴力check即可，一般模数可取1e9 + 7 或者 1e9 + 11；(一般哈希函数构造的模数也可选择这个)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
const ll mod = 1e9 + 7;
const ll mod1= 1e9 + 11;
ll a, b, c, d, e, f, g;
ll quick_mod(ll a, ll b, ll mod){
ll sum = 1;
while(b){
if(b & 1) sum = sum * a % mod;
a = a * a % mod;
b /= 2;
}
return sum;
}
void print(ll a, ll b, ll mod){
printf("down = %lld, up = %lld, ans = %lld\n", a, b, quick_mod(a, b, mod));
}
bool check(ll a, ll b, ll c, ll d, ll e, ll f, ll g, ll mod){
a %= mod;
b %= mod;
c %= mod;
ll t1 = quick_mod(a, d, mod);
ll t2 = quick_mod(b, e, mod);
ll t3 = quick_mod(c, f, mod);
if((t1 + t2 + t3) % mod == (g % mod)){
return true;
}
return false;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%lld%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &e, &f, &g);
if(check(a, b, c, d, e, f, g, mod1) && check(a, b, c, d, e, f, g, mod)){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}
H：施魔法
感受：一眼就出思路，可是由于当时卡E和G而且H题的一些细节也没完全搞清楚，就不敢写了
思路：贪心想，能量值肯定要排序，然后从小到大排序。dp[i]表示择优取前 i 个能量值的最小cost。
dp[i] = dp[0] + a[i] - a[1]
dp[i] = dp[1] + a[i] - a[2]
dp[i] = dp[2] + a[i] - a[3]
...
dp[i] = dp[j] + a[i] - a[j + 1] (i - j == k)
我们就可以线性更新dp[] - a[]的值;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
const ll inf = 1e18;
ll dp[maxn];///dp[i]表示取完前i个最少消耗魔力
ll a[maxn];
int n, k;
int main(){
scanf("%d%d", &n, &k);///注意这里不要读入文件末尾结束，会wa
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
sort(a + 1, a + n + 1);
for(int i = 1; i < k; i++) dp[i] = inf;
ll tmp = dp[0] - a[1];
dp[k] = tmp + a[k];
for(int i = k + 1; i <= n; i++){
dp[i] = a[i] - a[1];
tmp = min(tmp, dp[i - k] - a[i - k + 1]);
dp[i] = min(dp[i], tmp + a[i]);
}
printf("%lld\n", dp[n]);
return 0;
}I：建通道
感受：赛后看了一会，写几个样例，发现就是水题
思路：很显然，数字相同的点，肯定是连在一起（缩点），因为其价格为0.
那我们就考虑缩点后的点集，写出它们的二进制，从低位到高位贪心，如果低位中至少有一个1，有一个0。那我们就可以让那一位为1的与0连，为0的与1连。这就是最优的贪心策略。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
ll a[maxn];
int n, tot;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
sort(a + 1, a + n + 1);
tot = unique(a + 1, a + n + 1) - (a + 1);
int num_1, num_0;
ll ans = 0;
for(int i = 0; i < 30; i++){
num_1 = num_0 = 0;
for(int j = 1; j <= tot; j++){
if(a[j] & ((ll)1 << i)){
num_1++;
}
else{
num_0++;
}
}
if(num_1 != 0 && num_0 != 0){
ll cost = (ll)1 << i;
ans = cost * (tot - 1);
break;
}
}
printf("%lld\n", ans);
return 0;
}
J：求函数
感受：模板题，就是分析的时候稍微细心一点
思路：
例子:
观察可知，我们可以用线段树维护两个括号的值。具体怎么维护，观察发现，第一个括号值直接累乘即可，第二个括号可以用前一项的第二个括号值*该项第一个括号的值 + 该项第二个括号值
由
.
.
合并
由
.
.
合并
#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
struct Node{
ll f1;
ll f2;
}node[maxn << 2];
int n, m;
ll k[maxn], b[maxn];
void up(int o){
node[o].f1 = node[ls].f1 * node[rs].f1 % mod;
node[o].f2 = ((node[rs].f1 * node[ls].f2) % mod + node[rs].f2) % mod;
}
void build(int o, int l, int r){
if(l == r){
node[o].f1 = k[l];
node[o].f2 = b[l];
return ;
}
int mid = (l + r) / 2;
build(ls, l, mid);
build(rs, mid + 1, r);
up(o);
}
void update(int o, int l, int r, int x, ll k, ll b){
if(l == r){
node[o].f1 = k;
node[o].f2 = b;
return ;
}
int mid = (l + r) / 2;
if(mid >= x) update(ls, l, mid, x, k, b);
else update(rs, mid + 1, r, x, k, b);
up(o);
}
Node ans;
void query(int o, int l, int r, int x, int y){
if(l >= x && y >= r){
ans.f1 = ans.f1 * node[o].f1 % mod;
ans.f2 = (node[o].f1 * ans.f2 % mod + node[o].f2) % mod;
return ;
}
int mid = (l + r) / 2;
if(mid >= x) query(ls, l, mid, x, y);
if(y > mid) query(rs, mid + 1, r, x, y);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%lld", &k[i]);
}
for(int i = 1; i <= n; i++){
scanf("%lld", &b[i]);
}
build(1, 1, n);
for(int i = 1; i <= m; i++){
int opt;
scanf("%d", &opt);
if(opt == 1){
int l; ll K, B;
scanf("%d%lld%lld", &l, &K, &B);
update(1, 1, n, l, K, B);
}
else{
int l, r;
scanf("%d%d", &l, &r);
if(r < l) swap(l, r);
ans.f1 = 1; ans.f2 = 0;
query(1, 1, n, l, r);
printf("%lld\n", (ans.f1 + ans.f2) % mod);
}
}
return 0;
}
京公网安备 11010502036488号