2020CSP-J普及组复赛
https://ac.nowcoder.com/acm/contest/8848#question
A-优秀的拆分(power)
解法一：
任意一个自然数都可以拆分成若干个不同的2的幂次方的和，比如1100010100，相当于1不断向左移，而1向左移动一位就相当于乘2，题目说是正整次幂，所有二进制第一位不能为一，否则会加一，不和题意。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int main()
{
int n,res = 1;
int a[55],t = 0;
cin >> n;
if(n & 1) cout << "-1";
else{
while(n){
if(n&1) a[t++] = res;
res <<= 1;
n >>= 1;
}
for(int i = t-1; i >= 0; i--){
cout << a[i] << " ";
}
}
return 0;
} 解法二：先找出1-1e7中2幂次数有哪些，然后从后往前取 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int cnt = 0;
int a[55],n,vis[55],b[5500];
void init()
{
ll res = 2;
a[cnt++] = 2;
while(res <= 1e7){
res *= 2;
a[cnt++] = res;
}
}
int main()
{
init();
cin >> n;
if(n & 1) cout << "-1";
else{
int t = 0;
for(int i = cnt-1; i >= 0; i--){
if(n >= a[i]) {
b[t++] = a[i];
n -= a[i];
}
}
for(int i = 0; i < t; i++){
cout << b[i] << " ";
}
}
return 0;
} 解法三：DFS搜索，因为只有24个数，DFS+剪枝可以满足 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int cnt = 0;
int a[55],n,vis[55];
void init()
{
ll res = 2;
a[cnt++] = 2;
while(res <= 1e7){
res *= 2;
a[cnt++] = res;
}
}
int flag = 0;
int b[55];
void dfs(int res,int xb)
{
//cout << res << endl;
if((res <= 1 && res != 0) || flag == 1){
return;
}
if(res == 0){
flag = 1;
int t = 0;
for(int i = 0; i < cnt; i++){
if(vis[i]) b[t++] = a[i];
// cout << i << " ";
}
sort(b,b+t);
for(int i = t-1; i >= 0; i--){
cout << b[i] << " ";
}
return;
}
for(int i = 0; i < xb; i++){//因为先去了xb之后的数，接下来要取的数只能是1-xb-1 之间的数，这一步缺少会超时。
if(vis[i] || res < a[i]) continue;
vis[i] = 1;
dfs(res-a[i],i);
vis[i] = 0;
}
}
int main()
{
init();
cin >> n;
dfs(n,cnt-1);
if(!flag) cout << "-1" << endl;
return 0;
} B-直播获奖
思路：大根堆+小根堆，一般两者是在一起使用的。大根堆在左，小根堆在右，用小根堆的大小去维护获奖人数，每次输出小根堆的堆顶元素。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;
priority_queue<int,vector<int>,less<int> >q1;//大根堆
priority_queue<int,vector<int>, greater<int> >q2;//小根堆
int b[1000005];
int main()
{
int num = 0,n,w,x;
scanf("%d%d",&n,&w);
for(int i = 1; i <= n; i++){
scanf("%d",&x);
int hj_num = i*w/100;
hj_num = max(1,hj_num);
if((!q2.empty() && q2.top() <= x) || q2.empty()){
q2.push(x);
}
else q1.push(x);
while(q2.size() < hj_num){
int temp = q1.top();
q1.pop();
q2.push(temp);
}
while(q2.size() > hj_num){
int temp = q2.top();
q2.pop();
q1.push(temp);
}
printf("%d ",q2.top());
}
return 0;
}
D-放格取数：动态规划
dfs超时代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;
struct node{
int x,y;
node(int a,int b){
x = a;
y = b;
}
};
int dir[3][2] = {{-1,0},{1,0},{0,1}};
int vis[10005][10005];
ll a[10005][10005] = {0},ans = -ds;
int n,m;
bool check(int x,int y)
{
if(x <= 0 || x > n || y <= 0 || y > m) return false;
return true;
}
void dfs(int x,int y,ll l)
{
//cout << l <<endl;
// cout << x << y << endl;
if(x == n && y == m){
ans = max(l,ans);
// cout << ans << endl;
return;
}
for(int i = 0; i < 3; i++){
int dx = x + dir[i][0];
int dy = y + dir[i][1];
// cout << dx << dy << endl;
if(vis[dx][dy]) continue;
if(check(dx,dy)){
vis[dx][dy] = 1;
dfs(dx,dy,1ll*(l+a[dx][dy]));
vis[dx][dy] = 0;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%lld",&a[i][j]);
}
}
vis[1][1] = 1;
dfs(1,1,a[1][1]);
printf("%lld\n",ans);
return 0;
}
动态规划：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;
int n,m;
ll dp[1005][1005][2],a[1005][1005];
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%lld",&a[i][j]);
}
}
memset(dp, -0x3f, sizeof dp);
dp[1][0][0] = 0;
for(int j = 1; j <= m; j++){
for(int i = 1; i <= n; i++){
dp[i][j][0] = max(dp[i-1][j][0],max(dp[i][j-1][1],dp[i][j-1][0])) + a[i][j];
}
for(int i = n; i >= 1; i--){
dp[i][j][1] = max(dp[i+1][j][1],max(dp[i][j-1][0],dp[i][j-1][1])) + a[i][j];
}
}
printf("%lld",max(dp[n][m][1],dp[n][m][0]));
return 0;
}
