A 优秀的拆分
题意简述:
给定一个正整数，要求将其拆分成若干个数的和，满足这些数都可以表示为 (2^i) ((1leq ileq log{10^7}))。
题解:
我们都知道，任何一个正整数都可以被表示成若干个二的整数次幂的和，如 (12=2^3+2^2)，(18=2^4+2^1) 。但是根据题目要求，我们并不能使用 (2^0)。因此，假如数据的 (n) 为奇数，应当输出 (-1) 。判断完后，只要对 (n) 进行二进制分解即可，复杂度 (O(log n))。
代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int ans[41],top=0;//因为要求用从大到小输出，用栈存储答案
int main()
{
scanf("%d",&n);
if(n&1)
return puts("-1"),0;//不合法
while(n)
{
ans[++top]=n&-n; // 其中 lowbit，即 n&-n 可以求出目前最低一位的大小。
n-=n&-n; // 减去答案
}
while(top)
printf("%d ",ans[top--]);//输出
}
B 直播获奖
题意简述
按照给定的顺序插入 (n) 个正整数，要求出每次插入第 (i) 个数后，第 (lfloor{frac{i imes w}{100}} floor) 大的数的大小。
题解
我们可以想到通过堆来做这道题。我们可以开一个小根堆 (P)，来存储被选上的数字。再开一个大根堆 (Q)，来存储未被选上的数字。当 (P) 中的数字不足 (lfloor{frac{i imes w}{100}} floor) 个的时候，从 (Q) 中取数字放入 (P) 中。插入的时候，直接将数字放入 (Q) 中。此外，假如 (P) 顶的元素小于 (Q) 顶的元素，则交换两个堆顶的元素，这样可以保证 (P) 中任意数字大于等于 (Q) 中所有数字。输出的答案显然就是 (P) 的堆顶元素。复杂度 (O(nlog n))
代码
// 代码中的 p,q 与题解相反，请注意。
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
priority_queue<int> p;
int sz=0,w,n;
int main()
{
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++)
{
int mxsz=max(i*w/100,1);
int x;
scanf("%d",&x);
p.push(x);
while(sz<mxsz)
{
sz++;
q.push(p.top());
p.pop();
}
// 向 P 中丢入 Q 顶元素
while(q.top()<p.top())
{
int x=q.top(),y=p.top();
q.pop();
p.pop();
p.push(x);
q.push(y);
}
// 交换两堆堆顶元素
printf("%d ",q.top());
}
}
C 表达式
题意简述
给你一个后缀表达式，每次询问将一个数取反后这个后缀表达式的值。
题解
我们可以将这个表达式的表达式树建出来，令 (V_i) 为点 (i) 的子树的值， (T_i) 为点 (i) 的状态，(Fa_i)是点 (i) 的父亲节点，表达式树的点按照读入的顺序编号，且有 (n) 个点，当 (T_i=1) 时，则 (i) 取反会导致 (V_n) 取反。显然，(T_n=1)。转移的时候，假如点 (i) 非叶子节点，则点 (i) 一定是个运算符。
当点 (i) 操作符为 (not) 时，显然 (T_{Son_i}=T_i)。
当 (i) 为 (or) 时，若有一个子节点为 (1) 且另一个为 (0) 则值为 (1) 的 (T) 为 (1) 。如果两个都为 (1)，则所有儿子的 (T) 都为 (0)。若两个都为 (0) 则 (T) 都为 1。
当 (i) 为 (and) 的时候，讨论的东西与 (or) 恰好相反，就不在此赘述。
因此，只需要在建树后，从根节点 (n) 开始 dfs 一遍即可。复杂度 (O(|s|+q))
代码
#include<bits/stdc++.h>
using namespace std;
char s[1000010][8];
int fa[1000010],son[1000010][2],v[1000010];
bool vis[1000010];
int cnt=0;
int n,a[1000010],t[1000010],to[1000010];
int st[1000010],top=0;
int get(int x)
{
int len=strlen(s[x]+1);
int syn=0;
for(int i=2;i<=len;i++)
syn=syn*10+s[x][i]-'0';
return syn;
}
void query(int x)
{
int ls=v[son[x][0]],rs=v[son[x][1]];
if(s[x][1]=='x')
{
t[x]=1;
return ;
}
if(s[x][1]=='!')
{
query(son[x][0]);
return ;
}
if(s[x][1]=='|')
{
if(ls==0&&rs==1)
query(son[x][1]);
if(ls==1&&rs==0)
query(son[x][0]);
if(ls==0&&rs==0)
query(son[x][1]),query(son[x][0]);
return ;
}
if(s[x][1]=='&')
{
if(ls==0&&rs==1)
query(son[x][0]);
if(ls==1&&rs==0)
query(son[x][1]);
if(ls==1&&rs==1)
query(son[x][1]),query(son[x][0]);
return ;
}
}
int main()
{
while(1)
{
scanf("%s",s[++cnt]+1);
char c=getchar();
if(c!=' ')
break;
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=cnt;i++)
{
if(s[i][1]=='!')
{
son[i][0]=st[top];
fa[st[top--]]=i;
v[i]=!(v[son[i][0]]);
st[++top]=i;
}
else if(s[i][1]=='|')
{
son[i][0]=st[top];
fa[st[top--]]=i;
son[i][1]=st[top];
fa[st[top--]]=i;
v[i]=v[son[i][0]]|v[son[i][1]];
st[++top]=i;
}
else if(s[i][1]=='&')
{
son[i][0]=st[top];
fa[st[top--]]=i;
son[i][1]=st[top];
fa[st[top--]]=i;
v[i]=v[son[i][0]]&v[son[i][1]];
st[++top]=i;
}
else
st[++top]=i,v[i]=a[get(i)],to[get(i)]=i;
}
query(cnt);
int q;
scanf("%d",&q);
while(q--)
{
int x;
scanf("%d",&x);
printf("%d
",t[to[x]]^v[cnt]);
}
}
D 方格取数
题意简述
你想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，不能重复经过已经走过的方格，也不能走出边界。求经过的格子的数的和的最大值。
题解
一道显然的 dp 题。我们记录状态 (f_{i,j,k})，表示此时的你在第 (i) 行，第 (j) 列，从方向 (k) 处走过来，则有下面三条状态转移方程：
(f_{i,j,0}=max(f_{i,j+1,0},f_{i-1,j,1},f_{i+1,j,2})+V_{i,j})
(f_{i,j,1}=max(f_{i,j+1,0},f_{i-1,j,1})+V_{i,j})
(f_{i,j,2}=max(f_{i,j+1,0},f_{i+1,j,2})+V_{i,j})
(f_{n,m,k}=V_{n,m})
(f_{i,m+1,k}=f_{n+1,j,k}=f_{0,j,k}=f_{i,0,k}=-inf)
答案就是 (max(f_{1,1,0},f_{1,1,1},f_{1,1,2}))
代码
#include<bits/stdc++.h>
using namespace std;
long long f[1010][1010][3];
bool vis[1010][1010][3];
int v[1010][1010];
int n,m;
long long dfs(int x,int y,int opt)
{
if(x>n||y>m||x<1||y<1)
return -1e11; // 走出去了
if(x==n&&y==m)
return v[x][y]; //走到终点了
if(vis[x][y][opt])
return f[x][y][opt]; // 以前走过了
vis[x][y][opt]=1;
f[x][y][opt]=-1e11;
if(opt!=1)
f[x][y][opt]=max(dfs(x-1,y,2),f[x][y][opt]);
if(opt!=2)
f[x][y][opt]=max(dfs(x+1,y,1),f[x][y][opt]);
f[x][y][opt]=max(dfs(x,y+1,0),f[x][y][opt]);
// dp
f[x][y][opt]+=v[x][y];// 加上该点
return f[x][y][opt];
}
signed main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&v[i][j]);
printf("%lld
",dfs(1,1,0)); // 直接查询
}