T1-简单的乘法
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,m;
int a[N];
long double c[N] , pre[N];
long double maxn;
bool vis[N];
int cnt = 0;
void dfs(int k,int t,long double ans){
if( t>m ){
cnt ++ ;
maxn = max( ans , maxn);
return;
}
vis[k] = 1;
for(int i=1;i<=n;i++){
if( !vis[i] ){
dfs( i,t+1, (ans+a[i])*c[t] );
}
}
vis[k] = 0;
}
int main(){
freopen( "multi.in","r",stdin );
freopen( "multi.out","w",stdout );
cin>>n>>m;
bool flag = 1; //标记 c中元素是否全部大于0
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>c[i];
if( c[i] < 0 ) flag = 0;
}
if( n<=5 ) { // 测试点1~3，暴力枚举
long double ans = 0;
for(int i=1;i<=m;i++){ //没有搞清楚题目描述，所以取一种情况的结果初始话答案ans
ans = (ans+a[i])*c[i];
}
maxn = ans;
dfs(0,1,0);
cout << fixed << setprecision( 1 ) << maxn ;
}
else if( flag ){ //测试点 4~6 , 0<ci , 使用贪心策略
sort( a+1,a+n+1 );
pre[m+1] = 1 ;
for(int i=m;i>=1;i--){
pre[i] = pre[i+1]*c[i];
}
sort( pre+1,pre+m+1 );
long double ans = 0;
for(int i=m,j=n;i>=1;i--,j--){
ans += a[j]*pre[i];
}
cout << fixed << setprecision( 1 ) << ans ;
}
else{ //满分做法
sort( a+1,a+n+1 );
pre[m] = c[m] ;
for(int i=m-1;i>=1;i--){
pre[i] = pre[i+1]*c[i];
}
sort( pre+1,pre+m+1); // 按p值排序
long double ans = 0;
/*
a 0 1 2 3
p -2 -1 0 1 2
从上面的数组中可以很容易看出最优策略
*/
for(int i=1;i<=m;i++){
if( pre[i] <= 0 ){
ans += a[i]*pre[i];
}
else{
for(int j=m,k=n;j>=i;j--,k--){
ans += a[k]*pre[j];
}
break;
}
}
cout << fixed << setprecision( 1 ) << ans ;
}
fclose(stdin);
fclose(stdout);
return 0;
}
T2-0的个数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6;
int n;
ll a[N];
int main(){
freopen( "zero.in","r",stdin );
freopen( "zero.out","w",stdout );
cin>>n;
if( n<=10 ){ // 50分写法 ， 1<=n<=10 , 1<=ai<=10
ll re = 1;
for(int i=1;i<=n;i++){
cin>>a[i];
re*=a[i];
}
int cnt = 0;
while( re%10 == 0 ){
re/=10 ;
cnt++;
}
cout << cnt ;
}
else{ //满分写法， 唯一分解定理，统计2和5的个数num2,num5，取两者最小值
ll num2=0,num5=0;
int x;
for(int i=1;i<=n;i++){
cin>>a[i];
int tmp = a[i];
while( tmp%2==0 ) ++num2,tmp>>=1;
while( tmp%5==0 ) ++num5,tmp/=5;
}
cout << min( num2,num5 );
}
fclose(stdin);
fclose(stdout);
return 0;
}
T3-黑洞2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string s[200034];
ll n, m;
bool vis[50][50];
ll dx[4] = {-1, 1, 0, 0};
ll dy[4] = {0, 0, 1, -1};
vector<pair<ll, ll>> v;
bool check(ll x, ll y) { return x >= 0 && x < n && y >= 0 && y < m && s[x][y] != 'O'; }
//获取起点(sx,sy)的移动的偏移序列v
void dfs(ll x, ll y, ll sx,ll sy){
v.push_back({x - sx, y - sy});
vis[x][y] = 1;
for (ll i = 0; i < 4; i++) {
ll nx = x + dx[i];
ll ny = y + dy[i];
if (check(nx, ny) && !vis[nx][ny])
dfs(nx, ny, sx, sy);
}
}
bool f(ll x, ll y) {
memset(vis, 0, sizeof vis);
v.clear();
dfs(x, y, x, y);
//让其它每一个点按照(x,y)的偏移序列进行移动，验证是否会在按照(x,y)的移动过程中消失
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
if (s[i][j] == '.' && (i != x || j != y)) {
bool flag = true;
for (auto& p : v) { //模拟(i,j)的移动过程
ll nx2 = i + p.first;
ll ny2 = j + p.second;
if (!check(nx2, ny2)) { //消失后就可以停止移动
flag = false;
break;
}
}
if (flag) return false;//如果移动过程结束后，该点仍未消失，则不成立
}
}
}
return true;
}
void solve(){
cin >> n >> m;
for (ll i = 0; i < n; i++) cin >> s[i];
ll ans = 0;
for(ll i = 0; i < n; i++)
for(ll j = 0; j < m; j++)
if( s[i][j] == '.' && f(i, j) )
ans++;
cout << ans << '\n';
}
int main() {
freopen("blackhole.in", "r", stdin);
freopen("blackhole.out", "w", stdout);
ll t; cin >> t;
while (t --) solve();
fclose(stdin);
fclose(stdout);
return 0;
}
T4-植物大战僵尸
30分写法：贪心
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int t, n,m ;
int a[N],h[N],c[10];
int solve(){
memset( c,0,sizeof c );
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>h[i];
c[h[i]]++;
}
int k = 0;
while( true ){
int ak = a[k%n]; // 第k次的攻击力
if( ak==3 ){ // 3 6 5 4 2 1
if( c[3] ){
c[3]--;
}
else if( c[5] ){
c[5]--;
c[2]++;
}
else if( c[6] ){
c[6]--;
c[3]++;
}
else if( c[4]){
c[4]--;
c[1]++;
}
else if( c[2]){
c[2]--;
}
else if( c[1]){
c[1]--;
}
else return k;
}
else { // 2 1 4 5 6 3
if( c[2] ) c[2]--;
else if( c[1] ) c[1]--; //注意，如果没有血量为2的怪兽，那么应该优先处理血量为1的怪兽，因为攻击力2消灭血量为1的怪兽最合适
else if( c[4] ){
c[4]--;
c[2]++;
}
else if( c[5] ){
c[5]--;
c[3]++;
}
else if( c[6] ){
c[6]--;
c[4]++;
}
else if( c[3] ){
c[3]--;
c[1]++;
}
else return k;
}
k++;
}
}
int main(){
// 重定向标准输入输出到文件
freopen( "plant.in", "r", stdin); // 输入文件 "plant.in"
freopen( "plant.out", "w", stdout); // 输出文件 "plant.out"
cin>>t;
while(t--){
cout << solve() << endl;
}
// 关闭文件流
fclose(stdin);
fclose(stdout);
return 0;
}
50分写法：
对n==1的情况做出特殊判断即可
if( n==1 ){
long long ans = 0 , ak;
cin>>ak;
cin>>m;
for(int i=1;i<=m;i++){
cin>>h[i];
ans += (h[i]+ak-1)/ak;
}
return ans;
}
100分写法：贪心+二分
#include <bits/stdc++.h>
using namespace std;
const int N = 1000100;
using ll = long long; // 使用 long long 并简写为 ll
ll n; // 循环节长度
ll a[N]; // 存储循环节内的攻击序列：每个值为2或3
ll m; // 僵尸数量
ll h[N]; // 每个僵尸的生命值
ll p2[N]; // 前缀和数组：p2[i] 表示前i次攻击中造成2点伤害的次数
ll p3[N]; // 前缀和数组：p3[i] 表示前i次攻击中造成3点伤害的次数
ll H[N]; // 临时数组，用于在模拟过程中修改生命值（避免破坏原始数据）
/**
* 判断在给定 c2（2点伤害次数）和 c3（3点伤害次数）的情况下，
* 是否可以消灭所有僵尸。
*
* @param c2 可用的2点伤害攻击次数
* @param c3 可用的3点伤害攻击次数
* @return 是否能消灭全部僵尸
*/
bool ok(ll c2, ll c3) {
// 复制原始生命值到临时数组 H，以便后续修改
memcpy( H,h,sizeof h );
/*
* 第一阶段：优先使用3点伤害处理奇数血量且 >1 的僵尸
* 理由：如果一个僵尸血量是奇数（比如5），只用2点伤害会多出1点剩余（无法击杀）
* 所以需要至少一次3点伤害来补正。特别注意：血量为1的情况不需要3点伤害。
*/
for (ll i = 1; i <= m; i++) {
if ( H[i] % 2 == 1 && H[i] > 1 && c3) { // 血量为奇数且>1，并且还有3点伤害可用
H[i] -= 3;//血量减少3
c3--; // 消耗一次3点伤害
}
}
/*
* 第二阶段：批量处理每6点血量可以用两个3点伤害解决的问题
* 因为 3+3=6 正好消去6点血，效率最高。
* 尽可能多地将血量减少成不超过4的余数。
*/
for (ll i = 1; i <= m && c3 ; i++) {
ll x3 = H[i] / 6 * 2; // 最多能用多少次3点伤害来处理完整的6点段
ll use = min(c3, x3); // 实际可使用的3点伤害次数
H[i] -= 3 * use;
c3 -= use;
}
/*
* 第三阶段：处理剩余血量恰好为4的僵尸（最浪费3点伤害的情形）
* 因为4=2+2，最优策略是用两次2点伤害，但如果只剩3点伤害可用，
* 不得不用3点打一次（剩1血），所以这里先尝试用3点打4血僵尸，
* 避免留下无法处理的1血残血。
*/
// for (ll i = 1; i <= m && c3; i++) {
// if (H[i] == 4) {
// H[i] -= 3;
// c3--;
// }
// }
/*
* 将剩下的所有3点伤害转换为等效的2点伤害：
* 因为每次3点伤害可以视为“一次2点伤害 + 多出1点伤害”，
* 但既然已经尽可能用了3点伤，现在可以把它们当作2点伤来填补空白。
* 注意：此处是贪心的关键——只要总2点当量足够，就可以完成清理。
*/
c2 += c3; // 把剩余未用的3点伤害也当作“相当于提供c3次2点伤害”
c3 = 0;
/*
* 第四阶段：最后统一用2点伤害收尾
* 对于每个还没死的僵尸，计算所需最少2点伤害次数：ceil(H[i] / 2)
* 即 (H[i] + 1)/2 向上取整除以2
*/
for (ll i = 1; i <= m; i++) {
if (H[i] == 0) continue; // 已死亡，跳过
else {
ll x2 = (H[i] + 1) / 2; // ceil(H[i]/2)，即需要多少个2点伤害才能打死
if (c2 >= x2) {
c2 -= x2; // 消耗相应数量的2点伤害机会
H[i] = 0; // 僵尸被打死
} else {
return false; // 2点伤害不够，无法全清
}
}
}
return true; // 成功消灭所有僵尸
}
/**
* 解决单组测试用例
*/
void solve() {
cin >> n;
// 读入循环节的 n 个攻击数值
for (ll i = 1; i <= n; i++) {
cin >> a[i];
// 构建前缀和：
// p2[i]: 前i个攻击中有多少次伤害为2
// p3[i]: 前i个攻击中有多少次伤害为3
p2[i] = p2[i - 1] + (a[i] == 2);
p3[i] = p3[i - 1] + (a[i] == 3);
}
cin >> m; // 读入僵尸数量
for (ll i = 1; i <= m; i++) {
cin >> h[i]; // 读入每个僵尸的血量
}
// 二分查找最小攻击次数
ll l = 0, r = 1e18; // 设定搜索范围：从0到一个极大值
while (l < r) {
ll mid = (l + r) >> 1; // 二分中点
// 计算 mid 次攻击中总共产生的2点和3点伤害次数：
// 整周期部分：mid / n 个完整循环
// 剩余部分：mid % n 次攻击
ll c2 = mid / n * p2[n] + p2[mid % n]; // c2: 攻击力2的攻击次数；
ll c3 = mid / n * p3[n] + p3[mid % n]; // c3: 攻击力3的攻击次数；
if (ok(c2, c3)) {
r = mid; // 可行，尝试更小的次数
} else {
l = mid + 1; // 不可行，需增加攻击次数
}
}
cout << l << '\n'; // 输出最少攻击次数
}
int main() {
freopen( "plant.in", "r", stdin); // 输入文件
freopen( "plant.out", "w", stdout); // 输出文件
ll t;
cin >> t; // 读入测试数据组数
while (t--) {
solve(); // 处理每组数据
}
// 关闭文件流
fclose(stdin);
fclose(stdout);
return 0;
}