Codeforces 922 思维贪心 变种背包DP 质因数质数结论
2024-09-05 20:01:59
A
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#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 + ;
const int maxm = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll mod = 1e9 + ;
int main()
{
int x, y;
cin >> x >> y;
if (x == || y == )
{
if (x == && y == )
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return ;
}
int cur = y - ;
int remain = x - cur;
if (remain % == && cur && remain>=)
{
cout << "Yes" << endl;
return ;
}
cout << "No" << endl;
return ;
}
B
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#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[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll Mod = ;
int num[];
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 = ;
cin >> n;
for (int i = ; i < n; i++)
{
for (int j = i + ; 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 ;
}
C
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#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 = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
const int turn2[][] = {{, }, { -, }, {, }, {, -}, {, -}, { -, -}, {, }, { -, }};
//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 == && k <= )
{
cout << "Yes" << endl;
return ;
}
if (k >= n)
{
cout << "No" << endl;
}
else
{
for (ll i = ; i <= min(1LL * , k); i++)
{
if (n % i != i - )
{
cout << "No" << endl;
return ;
}
}
cout << "Yes" << endl;
}
return ;
}
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("!!!\n")
#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 = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
const int turn2[][] = {{, }, { -, }, {, }, {, -}, {, -}, { -, -}, {, }, { -, }};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
struct node
{
string str;
double per;
} s[];
bool operator <(node a, node b)
{
return a.per > b.per;
}
ll pre[];
string aim = "";
int main()
{
ll anser = ;
//freopen("sample.txt", "w", stdout);
int n;
cin >> n;
for (int i = ; i <= n; i++)
{
int now = ;
cin >> s[i].str;
int len = s[i].str.size();
for (int j = ; j < len; j++)
{
if (s[i].str[j] == 's')
{
now++;
}
}
if (len - now == )
{
s[i].per = ;
}
else
{
s[i].per = (double)now / (double)(len - now);
}
//cout << s[i].per << endl;
}
sort(s + , s + + n);
for (int i = ; i <= n; i++)
{
aim += s[i].str;
}
//cout << aim << endl;
int lenth = aim.size();
for (int i = ; i < lenth; i++)
{
if (i == )
{
pre[i] = (aim[i] == 's');
}
else
{
pre[i] = pre[i - ] + (aim[i] == 's');
}
if (aim[i] == 'h')
{
anser += pre[i];
}
}
cout << anser << endl;
return ;
}
E
一般想到的DP思路是DP[i][j]表示前i个用了j块钱能吸引多少鸟 但是这里j太大了(于是题目就提示你C[i]的总值不超过10000)
所以用DP[i][j]表示在前i个吸引了j个鸟最多好剩多少魔力 复杂度：
前面的复杂度是pre[i]较小的时候 后面是pre[i]较大的时候
DP方程：
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#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 = ;
const int turn[][] = {{, }, { -, }, {, }, {, -}};
const int turn2[][] = {{, }, { -, }, {, }, {, -}, {, -}, { -, -}, {, }, { -, }};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll n, W, B, X;
ll c[];
ll pre[];
ll cost[];
ll dp[][];
int main()
{
//freopen("sample.txt", "w", stdout);
// W初始值 B增加的上限 X回复的数目
mem(dp, -);
cin >> n >> W >> B >> X;
dp[][] = W;
for (int i = ; i <= n; i++)
{
cin >> c[i];
pre[i] = pre[i - ] + c[i];
}
for (int i = ; i <= n; i++)
{
cin >> cost[i];
}
for (ll i = ; i <= n; i++)
{
for (ll j = ; j <= pre[i]; j++)
{
for (ll k = ; k <= min(j, c[i]); k++)
{
if (dp[i - ][j - k] == - || 1LL * cost[i]*k > dp[i - ][j - k])
{
continue;
}
dp[i][j] = max(dp[i][j], dp[i - ][j - k] - 1LL * k * cost[i]);
}
if (dp[i][j] != -)
{
dp[i][j] = min(dp[i][j] + X, W + 1LL * j * B);
}
}
}
for (int i = pre[n]; i >= ; i--)
{
if (dp[n][i] >= )
{
cout << i << endl;
return ;
}
}
return ;
}
F
先N*lnN处理出每个数的被除数个数 然后做前缀和 如果K>dp[N] 就无解
所以猜测 当dp[i]>=k时即有解 当数据大于10时 dp数列每两个之间相差不会超过各自之下的i/2+1~i的质数个数(为什么选i/2~i的质数是因为其sum[i]只为1 方便调整)
所以当N>10的时候找到最小的满足dp[i]>=k的i 然后用删去其i/2+1~i之间的质数来调整 dp[i]-k
后来知道 当N<=10的时候 也满足>10的解法 一个数N的被整除数在N^(1/3)数量级 质数则在 N/LogN数量级
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#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[][] = {{, }, { -, }, {, }, {, -}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
ll Mod = ;
vector<int> prime;
int n;
ll k;
int anserten;
ll sum[];
ll dp[];
int visit[];
void dfs(int pos, int x)
{
if (pos == n + )
{
if (anserten == )
{
int now = ;
for (int i = ; i <= ; i++)
{
if (x & ( << i))
{
for (int j = i * ; j <= ; j += i)
{
if (x & ( << j))
{
//cout << i << " " << j << endl;
now++;
}
}
}
}
if (now == k)
{
anserten = x;
}
}
return ;
}
dfs(pos + , x + ( << pos));
dfs(pos + , x);
}
priority_queue<pair<int, int> > que;
int main()
{
cin >> n >> k;
for (int i = ; i <= n; i++)
{
for (int j = i * ; j <= n; j += i)
{
sum[j]++;
}
}
for (int i = ; i <= n; i++)
{
dp[i] = dp[i - ] + sum[i];
}
if (k > dp[n])
{
cout << "No" << endl;
return ;
}
else
{
cout << "Yes" << endl;
if (n <= )
{
dfs(, );
int anser = ;
for (int i = ; i <= ; i++)
{
if (anserten & ( << i))
{
anser++;
}
}
cout << anser << endl;
for (int i = ; i <= ; i++)
{
if (anserten & ( << i))
{
cout << i << " ";
}
}
cout << endl;
}
else
{
dp[n + ] = INT_MAX;
int aim;
for (aim = ; aim <= n; aim++)
{
if (dp[aim] >= k && dp[aim - ] < k)
{
break;
}
}
int anser = aim;
for (int i = aim; i >= ; i--)
{
visit[i] = ;
}
for (int i = aim; i >= aim / + ; i--)
{
que.push({sum[i], i});
}
int cha = dp[aim] - k;
pair<int, int> cnt;
while (cha > )
{
cnt = que.top();
que.pop();
if (cnt.first <= cha)
{
cha -= cnt.first;
visit[cnt.second] = ;
anser--;
}
}
cout << anser << endl;
for (int i = ; i <= aim; i++)
if (visit[i])
{
cout << i << " ";
}
cout << endl;
}
}
return ;
}
最新文章
- 自己封装的一个原生JS拖动方法。
- LEFT JOIN 多表查询的应用
- spring boot注解 --@EnableAsync 异步调用
- NDIS小鱼防火墙之拦截指定QQ登录
- 标准差（standard deviation）和标准误差（standard error）你能解释清楚吗？
- Linux Kernel 'perf_event.c'本地权限提升漏洞
- C语言-数据的快速引用
- 第九十六节，JavaScript概述
- VisualSFM+PMVS生成稠密点云
- java中volatile
- 安装和启动tftp-server服务器及可能出现Redirecting to /bin/systemctl restart xinetd.service问题的解决方式
- 星图智控推嵌入式家用AI摄像头
- Visual Studio 实用扩展工具
- angularjs为ng-click事件传递参数
- Python: find the smallest and largest value
- ethereum & ETC
- weblogica
- Spring框架中IoC(控制反转)的原理（转）
- 【黑金原创教程】【FPGA那些事儿-驱动篇I 】实验十：PS/2模块④ — 普通鼠标
- Java--static、final、static final的区别