Codeforces 965 枚举轮数贪心分糖果 青蛙跳石头最大流=最小割思想 trie启发式合并
2024-09-30 05:07:53
A
/*#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<cstdio>#include<cmath>#include<iostream>*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
int main()
{
int k, n, s, p;
cin >> k >> n >> s >> p;
int ans = n / s + ( - (n % s == ));
ans *= k;
cout << ans / p + ( - (ans % p == )) << endl;
return ;
}
B
/*#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<cstdio>#include<cmath>#include<iostream>*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
char f[][];
int ans;
int aimc = ;
int aimr = ;
int flag;
int now;
int main()
{
int n, k;
cin >> n >> k;
for (int i = ; i <= n; i++)
{
scanf("%s", f[i] + );
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if (f[i][j] == '#')
{
continue;
}
now = ;
for (int dx = j - k + ; dx <= j; dx++)
{
if (dx + k > n + )
{
break;
}
if (dx < )
{
continue;
}
flag = ;
for (int w = dx; w <= dx + k - ; w++)
{
if (f[i][w] == '#')
{
flag = ;
break;
}
}
if (flag)
{
now++;
}
}
for (int dy = i - k + ; dy <= i; dy++)
{
if (dy + k > n + )
{
break;
}
if (dy < )
{
continue;
}
flag = ;
for (int w = dy; w <= dy + k - ; w++)
{
if (f[w][j] == '#')
{
flag = ;
break;
}
}
if (flag)
{
now++;
}
}
if (now > ans)
{
ans = now;
aimc = i, aimr = j;
}
}
}
cout << aimc << " " << aimr << endl;
return ;
}
C
首先用贪心的思想可以知道 如果是一整轮一整轮地分 肯定是X越大越好
当加上题目剩下的不小于X的也要分的时候 最佳肯定是当X尽量大且最后多分给A1一次的时候最佳
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,k,m,d;
cin >> n >> k >> m >> d;
ll anser=;
for(ll i=;i<=d;i++)
{
if(i!=)
{
ll now=n/(i-);
if(now<k)
continue;
}
ll sum=n/(k*i-k+);
if(sum>m)
{
if(m*i>=(n-n%m)/k)
sum=m;
else
continue;
}
anser=max(anser,sum*i);
}
cout<<anser<<endl;
return ;
}
D
这题的建模是一个网络流 第i个石头对每个[i+1,i+l]都有一条容量为a[i]的边 源点与左岸相连 汇点与右岸相连 算最大流
但其实可以用最大流最小割思想简化 因为你跳的次序并不会影响最后的答案 所以我们可以认定每次全部青蛙都在一个长度为L的窗口内
所以答案就是min(sum(ai~ai+l)) 即视连续L个石头为一个节点 前一个节点有指向后一个节点sum(ai~ai+l)的边 所以最大流是最小的那条边
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[];
int main()
{
int n, l;
cin >> n >> l;
n--;
int minn = INT_MAX;
int sum = ;
for (int i = ; i < n; i++)
{
cin >> a[i];
}
for (int i = ; i < l; i++)
{
sum += a[i];
}
minn = sum;
for (int i = l; i <= n - ; i++)
{
sum -= a[i - l];
sum += a[i];
minn = min(minn, sum);
}
cout << minn << endl;
return ;
}
E
最新文章
- 项目游戏开发日记 No.0x000005
- MFC学习笔记(一)
- PSP(16/03/14-16/03/15)
- ESI 动态缓存技术
- html5学习小结,float练习。
- [Solution] 一步一步WCF(2) 终结点Endpoint
- C语言-04-函数
- 繁华模拟赛 Evensgn的债务
- webservice 错误::无法加载协定为的终结点配置部分,因为找到了该协定的多个终结点配置。请按名称指示首选的终结点配置部分。
- unity,生成的mac版游戏切场景时卡死解法
- mysql-备份和还原(普通还原和binlog还原)
- SQL Server Profiler监控执行语句
- [UWP]创建一个进度按钮
- nginx的反向代理功能和缓存功能
- 【3y】从零单排学Redis【青铜】
- .NET CAD二次开发学习 对称画线功能
- COGS 2353 2355 2356 2358 有标号的DAG计数
- LeetCode 709.To Lower Case
- 2109 ACM 排序
- liunx上安装MySQL一个非常简单的方法