Codeforces 922 思维贪心 变种背包DP 质因数质数结论
分类:
IT文章
•
2024-01-21 20:38:25
A
![]()
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!
")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 3e7 + 10;
const int maxm = 300;
const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll mod = 1e9 + 7;
int main()
{
int x, y;
cin >> x >> y;
if (x == 0 || y == 0)
{
if (x == 0 && y == 1)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}
int cur = y - 1;
int remain = x - cur;
if (remain % 2 == 0 && cur && remain>=0)
{
cout << "Yes" << endl;
return 0;
}
cout << "No" << endl;
return 0;
}
View Code
B
![]()
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!
")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll Mod = 1000000007;
int num[10000];
int cnt;
bool check(int a, int b, int c)
{
if (a + b > c && a + c > b && b + c > a)
{
return true;
}
return false;
}
int main()
{
int n;
int anser = 0;
cin >> n;
for (int i = 1; i < n; i++)
{
for (int j = i + 1; j <= n; j++)
{
int aim = (i ^ j);
if (aim >= j && aim <= n && check(i, j, aim))
{
//cout << i << " " << j << " " << aim << endl;
anser++;
}
}
}
cout << anser << endl;
return 0;
}
View Code
C
![]()
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!
")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int maxn = 100005;
const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const int turn2[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, -1}, { -1, -1}, {1, 1}, { -1, 1}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
int main()
{
//freopen("sample.txt", "w", stdout);
ll n, k;
cin >> n >> k;
if (n == 1 && k <= 2)
{
cout << "Yes" << endl;
return 0;
}
if (k >= n)
{
cout << "No" << endl;
}
else
{
for (ll i = 1; i <= min(1LL * 50, k); i++)
{
if (n % i != i - 1)
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
}
return 0;
}
View Code
D
奇葩贪心题 假设有两个字符串A B A在B前面的条件是什么？
假设A有SHa个sh BSHb A有Sa个s BSb A有Ha个h BHb 当 SHa+SHb+Sa*Hb>SHa+SHb+Sb*Ha 时成立
转换一下就是A的sh比例比B高的时候 A在B前面
![]()
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!
")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int maxn = 100005;
const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const int turn2[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, -1}, { -1, -1}, {1, 1}, { -1, 1}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
struct node
{
string str;
double per;
} s[100005];
bool operator <(node a, node b)
{
return a.per > b.per;
}
ll pre[100005];
string aim = "";
int main()
{
ll anser = 0;
//freopen("sample.txt", "w", stdout);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int now = 0;
cin >> s[i].str;
int len = s[i].str.size();
for (int j = 0; j < len; j++)
{
if (s[i].str[j] == 's')
{
now++;
}
}
if (len - now == 0)
{
s[i].per = 1000000;
}
else
{
s[i].per = (double)now / (double)(len - now);
}
//cout << s[i].per << endl;
}
sort(s + 1, s + 1 + n);
for (int i = 1; i <= n; i++)
{
aim += s[i].str;
}
//cout << aim << endl;
int lenth = aim.size();
for (int i = 0; i < lenth; i++)
{
if (i == 0)
{
pre[i] = (aim[i] == 's');
}
else
{
pre[i] = pre[i - 1] + (aim[i] == 's');
}
if (aim[i] == 'h')
{
anser += pre[i];
}
}
cout << anser << endl;
return 0;
}
View Code
![]()
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!
")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int maxn = 100005;
const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const int turn2[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, -1}, { -1, -1}, {1, 1}, { -1, 1}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll n, W, B, X;
ll c[1005];
ll pre[1005];
ll cost[1005];
ll dp[1005][10005];
int main()
{
//freopen("sample.txt", "w", stdout);
// W初始值 B增加的上限 X回复的数目
mem(dp, -1);
cin >> n >> W >> B >> X;
dp[0][0] = W;
for (int i = 1; i <= n; i++)
{
cin >> c[i];
pre[i] = pre[i - 1] + c[i];
}
for (int i = 1; i <= n; i++)
{
cin >> cost[i];
}
for (ll i = 1; i <= n; i++)
{
for (ll j = 0; j <= pre[i]; j++)
{
for (ll k = 0; k <= min(j, c[i]); k++)
{
if (dp[i - 1][j - k] == -1 || 1LL * cost[i]*k > dp[i - 1][j - k])
{
continue;
}
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] - 1LL * k * cost[i]);
}
if (dp[i][j] != -1)
{
dp[i][j] = min(dp[i][j] + X, W + 1LL * j * B);
}
}
}
for (int i = pre[n]; i >= 0; i--)
{
if (dp[n][i] >= 0)
{
cout << i << endl;
return 0;
}
}
return 0;
}
