A.翻转游戏
题目描述
-
以下为例:
bwbw wwww bbwb bwwb
这里$b$表示该格子放的物件黑色面朝上、$w$表示该格子放的物件白色朝上。如果我们选择翻转第三行的第一个物件,那么格子状态将变为:
游戏的目标是翻转到所有的物件白色朝上或黑色朝上。你的任务就是写一个程序来求最少的翻转次数来实现这一目标。
输入格式
输出格式
样例
#include <bits/stdc++.h>
using namespace std;
const int Inf=0x3f3f3f3f;
int ans,cnt;
char s[5][5],tmp[5][5];
void flip(char &ch) {
if(ch=='w') ch='b';
else ch='w';
}
void press(int i,int j) {
cnt++;//翻转+1
flip(tmp[i-1][j]);//更新上下左右和自己
flip(tmp[i][j-1]);
flip(tmp[i][j]);
flip(tmp[i][j+1]);
flip(tmp[i+1][j]);
}
void calc(int x,char ch) {
memcpy(tmp,s,sizeof(s));//将s数组赋于tmp数组
cnt=0;//计算翻转次数
for(int i=1;i<=4;i++) {
if(x&(1<<(i-1))) {//如果状态x第一行第i列状态为翻转
press(1,i);//翻转第一行第i列
}
}
for(int i=2;i<=4;i++) {
for(int j=1;j<=4;j++) {//由上一行状态推下一行翻转状态
if(tmp[i-1][j]!=ch) {//如果上一行第j列字母不符合所需字母,则此行第j列就需要反转
press(i,j);//翻转第i行第j列
}
}
}
for(int i=1;i<=4;i++) {//处理最后一行
if(tmp[4][i]!=ch) return;
}
ans=min(ans,cnt);
}
int main() {
ans=Inf;
for(int i=1;i<=4;i++) {
scanf("%s",s[i]+1);
}
int Maxn=(1<<4)-1;//枚举第一行状态
for(int i=0;i<=Maxn;i++) {
calc(i,'b');//矩阵全部反转为'b',(需第一行初始全为'b')
calc(i,'w');//矩阵全部反转为'w',(需第一行初始全为'w')
}
if(ans==Inf) printf("Impossible
");//若ans值未改变,则无符合条件反转次数
else printf("%d
",ans);//若初始已全为'b'或'w',ans途中也可变为0
return 0;
}
洛谷同款加强版:
题目链接:https://www.luogu.com.cn/problem/P1764
大概就是将$4 imes4$的矩阵改为$n imes n$的矩阵,$nleq16$
将代码里的$4$改为$n$,枚举$(1<<n)-1$个状态,但是会$TLE$一个点
加上空间换时间的$inline$不开O2优化,勉强从夹缝中通过
洛谷P2708硬币翻转
过上个题的时候还看见一道这个,就一起水过了
那就当个小常识记录一下吧
输入一个字符串为$0$或$1$,$1$为正面,$0$为反面
问从第一个开始,一起翻转前$i$个,需多少次才能都将硬币翻成正面$1$
代码很简短,就是去除连续重复的$0$或$1$,翻转次数k先设为长度$len-1$;
遇见重复的$k--$,末尾若为$0$,$k++$,不为$0$(就是正面)就不用翻转
代码如下:
#include <bits/stdc++.h>
using namespace std;
char s[10005];
int main() {
scanf("%s",s);
int len=strlen(s);
int k=len-1;
for(int i=1;i<len;i++) {
if(s[i]==s[i-1]) k--;
}
if(s[len-1]=='0') k++;
printf("%d
",k);
return 0;
}
B.抢掠计划(也是元宵节卖汤圆那个题)
$tarjan$解释就...
先放个代码吧丑陋的我自己都不想看
#include <bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int x,y,S,P,sum,cnt,tot,head[maxn],to[maxn],next[maxn],dfn[maxn],xx[maxn],yy[maxn],a[maxn],dd[maxn],tree[maxn],ll[maxn],pp[maxn],ii[maxn],v[maxn];
stack<int> stk;
void add(int x,int y) {
to[++cnt]=y;
next[cnt]=head[x];
head[x]=cnt;
}
void Tarjan(int x) {
dfn[x]=ll[x]=++sum;
ii[x]=1;
stk.push(x);
for(int i=head[x];i;i=next[i]) {
if(!dfn[to[i]]) {
Tarjan(to[i]);
ll[x]=min(ll[x],ll[to[i]]);
}
else if(ii[to[i]]) ll[x]=min(ll[x],dfn[to[i]]);
}
if(ll[x]==dfn[x]) {
int ans=0;
tot++;
while(ans!=x) {
ans=stk.top();
stk.pop();
ii[ans]=0;
tree[ans]=tot;
v[tot]+=a[ans];
}
}
}
void Spfa() {
queue<int> q;
q.push(tree[S]);
dd[tree[S]]=v[tree[S]];
while(!q.empty()) {
int ans=q.front();
q.pop();
pp[ans]=0;
for(int i=head[ans];i;i=next[i]) {
if(dd[to[i]]<dd[ans]+v[to[i]]) {
dd[to[i]]=dd[ans]+v[to[i]];
if(!pp[to[i]]) {
pp[to[i]]=1;
q.push(to[i]);
}
}
}
}
int ans=0;
for(int i=1;i<=P;i++) {
scanf("%d",&x);
ans=max(ans,dd[tree[x]]);
}
printf("%d",ans);
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&xx[i],&yy[i]);
add(xx[i],yy[i]);
}
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
scanf("%d%d",&S,&P);
for(int i=1;i<=n;i++) {
if(!dfn[i]) Tarjan(i);
}
memset(head,0,sizeof(head));cnt=0;
for(int i=1;i<=m;i++) {
x=xx[i],y=yy[i];
if(tree[x]!=tree[y]) add(tree[x],tree[y]);
}
Spfa();
return 0;
}
C.测绘
由于有些地方复制不过来就是懒,那就再次口述一下题目大意吧,也算复习一遍了
测量$n$次气压,依次为$M_i$,限制误差值$E$
选取最少的$K$次测量数据,使其误差小于等于$E$;
在选择$K$次测量数据的条件下,输出最小的误差值
计算误差要求:
选择$K$次测量数据的序列设为$S_1,S_2... ...S_K$
未被选择的测量数据:
1.如果其下标$i$小于$S_1$,它的误差值为$2 imes|M_i-M_{S_1}|$
2.如果其下标$i$大于$S_K$,它的误差值为$2 imes|M_i-M_K|$
3.如果$i$介于其之间,若介于$S_j$和$S_{j+1}$之间,它的误差值为$|2*M_i-M_j-M_j+1|$
线性$dp$
设置一个$pre[][]$数组并对其进行预处理:
对于$pre[i][0]$,左边界为$i$的向左延伸的误差值之和;
$pre[i][n+1]$,右边界为$i$的向右延伸的误差值之和;
$pre[i][j]$,所选序列中$i$到$j$为连续的,$i$到$j$之间的误差值之和
$dp[i][j]$记录前$i$个数选取$j$个数的误差值之和,(由于转移方程的需要,选取的$j$个数里面一定有第$i$个数)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100+10;
const ll Inf=0x3f3f3f3f3f3f3f3f;
int n,E,K,a[maxn];
ll ans,dp[maxn][maxn],pre[maxn][maxn];
int main() {
scanf("%d%d",&n,&E);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++) {//此循环均为pre[][]数组的预处理
for(int j=i+1;j<=n;j++) {
for(int k=i+1;k<=j-1;k++) {
pre[i][j]+=abs(2*a[k]-a[i]-a[j]);
}
}
for(int j=1;j<i;j++) {
pre[i][0]+=2*abs(a[j]-a[i]);
}
for(int j=i+1;j<=n;j++) {
pre[i][n+1]+=2*abs(a[j]-a[i]);
}
}
ans=Inf,K=n;
for(int i=1;i<=n;i++) {
dp[i][1]=pre[i][0]+pre[i][n+1];
if(dp[i][1]<=E) {
K=1;
ans=min(ans,dp[i][1]);
}
}
if(K==1) {
printf("%d %lld
",K,ans);
return 0;
}
for(int i=2;i<=n;i++) {//选取i个数
for(int j=i;j<=n;j++) {//前j个数
dp[j][i]=Inf;
for(int k=i-1;k<j;k++) {
dp[j][i]=min(dp[j][i],dp[k][i-1]-pre[k][n+1]+pre[k][j]+pre[j][n+1]);
}
if(dp[j][i]<=E) {
if(i==K) ans=min(ans,dp[j][i]);//选取K个数的状态下,求得最小的误差值之和
if(i<K&&dp[j][i]!=Inf) {//选取i个数小于K个数,且dp[j][i]于此状态下已发生过动态转移(实际上应该是一个初始位置吧)
//就更新K的值,将dp[j][i]赋于ans
K=i;
ans=dp[j][i];
}
}
}
if(K!=n) {//如果K值已被更新,就是选取i个数;由于前j个数和小k循环已跑完,此时的ans为选取K个数的最小误差值之和,可以直接输出结束程序
printf("%d %lld
",K,ans);
return 0;
}
}
printf("%d %lld
",K,ans);//题目满足一定有这样的一个序列满足小于等于最大误差值E,如果K<n当中均未输出,就选取K=n个数,ans(误差值)为0;
return 0;
}
D.奖学金
题目描述
猪仙发现人类可以上很多大学,而猪们却没有大学可上。为了解决这个问题,于是他创立了一所大学,取名为猪仙大学。
为了选拔合适的学生入学,他发明了一种学术能力测试(简称$CSAT$),这种测试的分数异常精确,每头猪的成绩可以用$1$到$2,000,000,000$之间的一个整数表示。
猪仙大学的学费很贵(猪仙比较黑),很多猪都负担不起,他们需要申请一些奖学金($1leq$ 奖学金$leq10000$)。可是政府并没有为猪准备奖学金,于是所有的预算都必须要从学校自身有限的基金中间扣除(设基金总额为$F,0leq Fleq2,000,000,000$)。
更槽的事,猪仙大学的只有$N(1leq Nleq19999)$间教室,$N$是一个奇数,而一共有$C(Nleq Cleq100,000)$头猪申请入学,为了让最多的猪接受教育,猪仙打算接受$N$头猪的申请,而且她还想让这些猪$CAST$成绩的中位数尽可能地高。
输入格式
第一行:三个用空格分开的整数:$N,C$和$F$。
第二行到$C+1$行:每行有两个用空格分开的整数。第一个数是这头猪的$CAST$成绩,第二个数是这头猪想申请的奖学金。
输出格式
第一行:一个整数,表示猪仙可以得到的最大中位数,如果现有基金不够资助$N$头猪,则输出$-1$。
因为$N$为奇数,所以中位数处于所选猪序列当中的$N/2+1$的位置
可将求解答案的过程中分解为两个子问题:
1.将整个猪序列按照成绩由高到低排列,顺次枚举最大中位数,满足条件就退出
2.所枚举的中位数位置为$i$,第$i$头猪的奖学金加上$i-1$左边的$n/2$个最小奖学金之和and $i+1$右边的$n/2$个最小奖学金之和就是当前中位数条件下所得的最小奖学金数之和;
满足的条件即为$suml[i-1]+sumr[i+1]+e[i].moneyleq E$
求解左端和右端的最小奖学金之和,可用优先队列(默认顶位置为最大值),自动插入排序
没了没了 有个遗留:分数相等时,奖学金大小的先后顺序对答案貌似没有影响...
还有个问题,洛谷上的数据范围是$2e5+10$,开$1e5+10$会$RE$三个点,我还以为我边界判断错误了
洛谷提交地址:https://www.luogu.com.cn/problem/P3963
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,C;
typedef long long ll;
ll F,sum,suml[maxn],sumr[maxn];
priority_queue<int>q;
struct Edge{
ll mark,money;
}e[maxn];
bool comp(Edge A,Edge B) {
return A.mark>B.mark;
}
int main() {
scanf("%d%d%lld",&n,&C,&F);
for(int i=1;i<=C;i++) {
scanf("%lld%lld",&e[i].mark,&e[i].money);
}
sort(e+1,e+1+C,comp);//按mark由大到小排序
n/=2;
sum=0;
for(int i=1;i<=n;i++) {//suml[n]时,1~n全部加上
sum+=e[i].money;
q.push(e[i].money);
}
suml[n]=sum;
for(int i=n+1;i<=C-n-1;i++) {
if(q.top()>e[i].money) {//如果第i头猪的奖学金小于顶端,pop顶端,push该奖学金
//因为i++,所以每次只需替换一个,插入之后优先队列自动排序找地插入,顶端永远为最大值
sum+=e[i].money;
sum-=q.top();
q.pop();
q.push(e[i].money); //以上都是交换更新操作
}
suml[i]=sum;//由i向左选取n/2头猪奖学金最小和
}
sum=0;
while(!q.empty()) q.pop();//清空队列
for(int i=C;i>=C-n+1;i--) {//sumr[C-n+1]时,C-n+1~C全部加上
sum+=e[i].money;
q.push(e[i].money);
}
sumr[C-n+1]=sum;
for(int i=C-n;i>=n+2;i--) {//与上操作雷同,只不过由末尾往前一次推,i--
if(q.top()>e[i].money) {
sum+=e[i].money;
sum-=q.top();
q.pop();
q.push(e[i].money);
}
sumr[i]=sum;//由i向右选取n/2头猪最小奖学金之和
}
for(int i=n+1;i<=C-n;i++) {//mark由大到小枚举
if(suml[i-1]+sumr[i+1]+e[i].money<=F) {//满足所需奖学金小于等于可提供基金,就不再往下枚举,此时的mark即为最大中位数
printf("%lld
",e[i].mark);
return 0;
}
}
printf("-1
");
return 0;
}
下午写完之后交上去$90$,是因为最后判断时右边界写错了
中位数最大可达$C-n$,写成了$C-n+1$(枚举中位数的范围$n+1~C-n$)
for(int i=n+1;i<=C-n;i++) {
if(suml[i-1]+sumr[i+1]+e[i].money<=F) {
printf("%lld
",e[i].mark);
return 0;
}
}
接下来说点闲篇,就当给自己记录了
----------------------------------------
$ps:$
中午午歌的时候听了$monsters$
还记得那句话$I$ $love$ $you$ $three$ $thousand$ $times.$