【2013南京区域赛】部分题解 hdu4802—4812

2023-11-09 15:40
文章标签 区域 部分 题解 2013 南京 hdu4802 4812

本文主要是介绍【2013南京区域赛】部分题解 hdu4802—4812，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

上周末打了一场训练赛，题目是13年南京区域赛的

这场题目有好几个本来应该是我擅长的，但是可能是太久没做比赛了各种小错误代码写的也丑各种warusn trush搞得人很不爽

全场题之一的1002也没有想出来，最终只出了三题连铜牌线都没有达到，心好累

赛后又补了三道题，还是写一下题解毕竟好久都没写了

 

1001：

全场题，队长秒过

代码：

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;string rk[] =   {"A", "A-", "B+", "B", "B-", "C+", "C", "C-", "D", "D-", "F" , "P", "N"};
double score[] = {4.0, 3.7,   3.3, 3.0,  2.7,  2.3, 2.0,  1.7, 1.3,  1.0,  0  , -1, -1};double getScore(string r)
{for(int i=0;i<11;i++)if(r == rk[i])return score[i];return 0;
}int main()
{int n;while(~scanf("%d", &n)){int sum = 0;double tot = 0;for(int i = 0; i < n; i++){int w;string r;cin >> w >> r;if(r!="P" && r!="N"){sum += w;tot += w * getScore(r);}}if(sum == 0)cout << "0.00" << endl;elseprintf("%.2f\n", tot / sum);}return 0;
}
View Code

 

1002：

题意：x，y初始都是1，给定一个目标 xn,yn，现有两种操作，求达到目标状态的最小操作数（只要最终y的整数部分等于yn即可）

        操作1：y++，y+=y/x (小数除法)

        操作2：x++；

分类：数学、贪心

做法：首先已知xn可求得操作2的数目，而观察操作1可知越早执行操作1 y提升的越快，所以从x=1到x=xn-1的过程中贪心的执行操作1即可 （在不达到yn+1的限制下早执行的越多越好）

代码：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<ctype.h>
using namespace std;
#define MAXN 10000
const double eps=1e-2;
double lim,y;
int x;
double p[12];
int main()
{while(scanf("%d%lf",&x,&y)!=EOF){for(int i=1; i<x; i++){p[i]=1;for(int j=i; j<x; j++){p[i]+=p[i]/j;}}lim=y+1-eps;long long ans=0;y=1;for(int i=1; i<x; i++){y+=y/i;}if(y>lim){puts("-1");continue;}double now=1;for(int i=1; i<x; i++){int tmp=(floor)((lim-y)/(p[i]));ans+=tmp;y+=p[i]*tmp;ans++;}ans+=(floor)(lim-y);printf("%I64d\n",ans);}return 0;
}
View Code


1003：

题意：要往一个方格构成的矩形上铺满1*1，1*2的砖，有些地方不能铺，且1*1的数量有限制，求方案数。

分类：状压dp

做法：很基础的状压dp，有人说是插头但是我觉得比变态插头简单多了，直接三维dp就好了，转移我用的是dfs。挺好理解的。

比赛的时候先被卡内存，改滚动数组又被卡常数了，后来又因为没注意边界条件导致访问非法内存warush，真是xnmbyy

代码:

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
const int mod=1e9+7;
int dp[2][1<<12][22];
char s[110][12];
int a[110][12];
int p[12];
int n,m;
int c,d;
bool can(int x,int s)
{for(int i=0; i<m; i++){if(((1<<i)&s)&&(!a[x][i]))return 0;}return 1;
}
void dfs(int x,int y,int num,int s,int pre)
{if(num>d)return;if(y==m){dp[x%2][s][num]+=pre;dp[x%2][s][num]%=mod;return;}if(p[y]!=-1){dfs(x,y+1,num,s,pre);return;}dfs(x,y+1,num+1,s,pre);dfs(x,y+1,num,s|(1<<y),pre);if(y<m-1&&(p[y+1]==-1)){dfs(x,y+2,num,s,pre);}
}
int main()
{//freopen("in.txt","r",stdin);while(scanf("%d%d%d%d",&n,&m,&c,&d)!=EOF){memset(dp,0,sizeof(dp));dp[0][0][0]=1;for(int i=1; i<=n; i++){scanf("%s",s[i]);for(int j=0; j<m; j++){a[i][j]=s[i][j]=='1';}}for(int i=1; i<=n; i++){for(int j=0; j<(1<<m); j++){for(int t=0; t<=d; t++){if(can(i,j)){memset(p,-1,sizeof(p));for(int k=0; k<m; k++){if(((1<<k)&j)||(a[i][k]==0)){p[k]=0;}}dfs(i,0,t,0,dp[(i-1)%2][j][t]);}}}memset(dp[(i-1)%2],0,sizeof(dp[(i-1)%2]));}long long ans=0;for(int i=c;i<=d;i++){ans+=dp[n%2][0][i];ans%=mod;}printf("%I64d\n",ans);}return 0;
}
View Code


1008：

题意：把一个树上的节点随机分给三个人，然后把链接不同两人的边断掉，每个人的得分是max(0,x-y) 其中x代表他拥有的大小为奇数的连通分量个数，y是偶数

        求三人得分*3^n 的期望

分类：树形dp

做法：首先yy得出三人得分和其实就是单人得分的期望的3倍，然后进行treedp算出一个的得分就好了，dp保存每个点是否取，取后当前连通分量的奇偶，以及x-y的值，

        转移还是比较好想的，刚好题目要输出*3^n的 所以避免了浮点数，这点还算比较良心

        hdu可惜又卡常数了，一定是我写的太挫

代码：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
#include<vector>
using namespace std;
#define MAXN 10000
const int mod=1e9+7;
long long dp[310][3][800];
long long tmp[3][705];
int h[310];
int l[310];
vector<int> g[310];
int n;
void dfs(int now,int pre)
{if(now){dp[now][1][350]=1;dp[now][0][350]=2;}elsedp[now][0][350]=3;h[now]=l[now]=0;for(int i=0; i<g[now].size(); i++){int to=g[now][i];if(to==pre)continue;dfs(to,now);for(int xy=l[now]; xy<=h[now]; xy++){for(int j=l[to]; j<=h[to]; j++){tmp[0][350+xy+j]+=dp[now][0][350+xy]*dp[to][0][350+j]%mod;tmp[1][350+xy+j]+=dp[now][1][350+xy]*dp[to][0][350+j]%mod;tmp[1][350+xy+j]+=dp[now][1][350+xy]*dp[to][2][350+j]%mod;tmp[1][350+xy+j]+=dp[now][2][350+xy]*dp[to][1][350+j]%mod;tmp[2][350+xy+j]+=dp[now][2][350+xy]*dp[to][2][350+j]%mod;tmp[2][350+xy+j]+=dp[now][2][350+xy]*dp[to][0][350+j]%mod;tmp[2][350+xy+j]+=dp[now][1][350+xy]*dp[to][1][350+j]%mod;tmp[0][350+xy+j+1]+=dp[now][0][350+xy]*dp[to][1][350+j]%mod;tmp[0][350+xy+j-1]+=dp[now][0][350+xy]*dp[to][2][350+j]%mod;}}for(int xy=-300 ;xy<=300; xy++){for(int j=0; j<=2; j++){dp[now][j][xy+350]=tmp[j][350+xy]%mod;if(dp[now][j][xy+350]){h[now]=max(h[now],xy);l[now]=min(l[now],xy);}}}memset(tmp,0,sizeof(tmp));}
}
int main()
{while(scanf("%d",&n)!=EOF){memset(dp,0,sizeof(dp));for(int i=0; i<=300; i++){g[i].clear();}for(int i=0; i<n-1; i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}g[0].push_back(1);dfs(0,0);long long ans=0;for(int xy=0; xy<=300; xy++){ans+=dp[0][0][350+xy]%mod*xy%mod;ans%=mod;}printf("%I64d\n",ans);}return 0;
}
View Code

1009：

题意：有n个数，对于k=1~n，求所有c(n,k)种组合分别异或之后的和

分类：dp

做法：按二进制展开，对每一位进行一个n^2的dp求出所有组合中当前位为1的有多少个，加入答案即可，然后这题我又被卡啦= =dp数组降了一维勉强才过

代码：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
const int mod=1e6+3;
int n;
long long a[1010];
long long dp[1010][2];
long long ans[1010];//适用于正负整数
template <class T>
inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0; //EOFwhile(c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return 1;
}inline void out(long long x) {if(x>9) out(x/10);putchar(x%10+'0');
}int main()
{//freopen("in.txt","r",stdin);while(scanf("%d",&n)!=EOF){memset(ans,0,sizeof(ans));for(int i=1; i<=n; i++){scanf("%I64d",a+i);//scan_d(a[i]);
        }for(int i=0; i<63; i++){memset(dp,0,sizeof(dp));dp[0][0]=1;for(int j=1; j<=n; j++){for(int k=j-1; k>=0; k--){/*dp[j][k][0]+=dp[j-1][k][0];dp[j][k][0]%=mod;dp[j][k][1]+=dp[j-1][k][1];dp[j][k][1]%=mod;*/if(a[j]&(1LL<<i)){dp[k+1][1]+=dp[k][0];dp[k+1][1]%=mod;dp[k+1][0]+=dp[k][1];dp[k+1][0]%=mod;}else{dp[k+1][1]+=dp[k][1];dp[k+1][1]%=mod;dp[k+1][0]+=dp[k][0];dp[k+1][0]%=mod;}}}for(int j=1; j<=n; j++){if(dp[j][1]>=1){ans[j]+=(1LL<<(i))%mod*dp[j][1]%mod;ans[j]%=mod;}}}for(int i=1; i<=n; i++){printf("%I64d%c",ans[i],i==n?'\n':' ');}}return 0;
}
View Code

1010：
题意：有三种颜色的小球（给定数量），每放一个球的得分等于前面和后面不同的颜色数

分类：贪心

做法：贪心，先尽量在前后多放不同颜色的球，剩下的填在中间即可，坑点是好多特判，容易忘某个细节

代码：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
long long a[3];
int main()
{// freopen("in.txt","r",stdin);while(scanf("%I64d%I64d%I64d",a,a+1,a+2)!=EOF){sort(a,a+3);long long ans=0;if(a[0]>=2){a[0]-=2;a[1]-=2;a[2]-=2;ans=15;ans+=(a[2]+a[1]+a[0])*6;cout<<ans<<endl;continue;}if(a[0]==1){a[0]-=1;a[1]-=1;a[2]-=1;ans=3;if(a[1]){a[1]--;a[2]--;ans+=7;ans+=(a[1]+a[2])*5;cout<<ans<<endl;continue;}if(a[2]){a[2]--;ans+=3;ans+=a[2]*4;cout<<ans<<endl;continue;}cout<<ans<<endl;continue;}if(a[1]){a[1]--;a[2]--;ans=1;if(a[1]){a[1]--;a[2]--;ans+=5;ans+=(a[1]+a[2])*4;cout<<ans<<endl;continue;}if(a[2]){a[2]--;ans+=2;ans+=(a[2])*3;cout<<ans<<endl;continue;}cout<<ans<<endl;continue;}if(a[2]>1){a[2]-=2;ans=1;ans+=(a[2])*2;}cout<<ans<<endl;}return 0;
}
View Code

1011：

题意：N个点的树，，每个点对应一个权值，，找出a 到b路径上吧权值的乘积%mod== K 的点对。。如果有多个输出字典序最小的那个。。。

分别是 求重心 然后分治，，查询的时候要 用到时间戳。。同时要预处理出逆元。。

(x*y) %mod == K ,,那么x = K*inv[y]%mod;

代码：

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1e5+10;
const int mod = 1e6+3;
int inv[mod];
int pow(int a, int n)
{int res = 1;while (n > 0){if (n & 1)res = ((ll)res * a) % mod;a = ((ll)a * a) % mod;n >>= 1;}return res;
}
void Get_inv()
{for (int i = 0; i < mod; i++)inv[i] = pow(i, mod-2);
}
int N, K, tot, head[maxn];
struct Edge
{int to, next;
} e[maxn << 1];
void add_edge(int x, int y)
{e[tot].to = y;e[tot].next = head[x];head[x] = tot++;
}
bool vis[maxn];
int siz[maxn], mstree[maxn], gravity;
void FindGravity(int r, int father, int cnt)
{siz[r] = 1;mstree[r] = 0;int maxv = 0;for (int i = head[r]; ~i ; i = e[i].next){int v = e[i].to;if (vis[v] == true || v == father)continue;FindGravity(v, r, cnt);siz[r] += siz[v];mstree[r] = max(mstree[r], siz[v]);}mstree[r] = max(mstree[r], cnt - siz[r]);if (mstree[gravity] > mstree[r])gravity = r;
}int top, S[maxn], idx[maxn], has[mod], has_idx[mod], val[maxn];
void Get_mul(int r, int father, int d)
{S[top] = d % mod;idx[top++] = r;for (int i = head[r]; ~i; i = e[i].next){int v = e[i].to;if (v == father || vis[v] == true)continue;Get_mul(v, r, (ll)d * val[v]%mod);}
}
int ans[2];
void update (int x, int y)
{if (x > y)swap(x, y);if (ans[0] > x)ans[0] = x, ans[1] = y;else if (ans[0] == x && ans[1] > y)ans[1] = y;
}
int time;         //时间戳
void update_hash(int value, int p)
{if (has[value] == time)                       //时间戳判断是否在同一深度的递归has_idx[value] = min(has_idx[value], p);else{has[value] = time;has_idx[value] = p;}
}
void solve (int r)
{time++;vis[r] = true;for (int j = head[r]; ~j; j = e[j].next){int v = e[j].to;if (vis[v] == true)continue;top = 0;Get_mul(v, r, val[v]);for (int i = 0; i < top; i++){if ((ll)S[i]*val[r]%mod == K)update(idx[i], r);int tmp = (ll)K *inv[(ll)S[i]*val[r]%mod]%mod;if (has[tmp] == time)update(has_idx[tmp], idx[i]);}for (int i = 0; i < top; i++){update_hash(S[i],idx[i]);}}for (int i = head[r]; ~i; i = e[i].next){int v = e[i].to;if (vis[v] == true)continue;gravity = 0;mstree[0] = N;FindGravity(v, r, siz[v]);solve(gravity);}
}void init()
{memset(head, -1, sizeof(head));memset(vis, false, sizeof(vis));memset(has, 0, sizeof(has));gravity = tot = time = 0;mstree[0] = N;ans[0] = ans[1] = inf;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);/*本地扩栈、*/int stksize = 256 << 20;char *pointer = (char *)malloc(stksize) + stksize;__asm__ ("movl %0,%%esp"::"r"(pointer));//64λ movq %0,%%rsp
#endifGet_inv();while (~scanf ("%d%d", &N,&K)){init();for (int i = 1; i <= N; i++)scanf ("%d", val+i);for (int i = 0; i < N-1; i++){int u, v;scanf ("%d%d", &u, &v);add_edge(u, v);add_edge(v, u);}FindGravity(1, 0, N);solve(gravity);if (ans[0] == inf)printf("No solution\n");elseprintf("%d %d\n", ans[0], ans[1]);}return 0;
}
View Code

 

转载于:https://www.cnblogs.com/oneshot/p/4362768.html

这篇关于【2013南京区域赛】部分题解 hdu4802—4812的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/377037。

相关文章

一文详解如何在Python中从字符串中提取部分内容

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》：本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST（抽象语法树）、字符串操作... 目录前言解决方案方法一：使用正则表达式方法二：使用 Pyparsing方法三：使用 AST方法四：使用字
阅读更多...
Mysql删除几亿条数据表中的部分数据的方法实现

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...
rtmp流媒体编程相关整理2013(crtmpserver,rtmpdump,x264,faac)

rtmp流媒体编程相关整理2013(crtmpserver,rtmpdump,x264,faac)

转自：http://blog.163.com/zhujiatc@126/blog/static/1834638201392335213119/ 相关资料在线版(不定时更新，其实也不会很多，也许一两个月也不会改) http://www.zhujiatc.esy.es/crtmpserver/index.htm 去年在这进行rtmp相关整理，其实内容早有了，只是整理一下看着方
阅读更多...
笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel

笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel

kernel起始与ENTRY(stext)，和uboot一样，都是从汇编阶段开始的，因为对于kernel而言，还没进行栈的维护，所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用，前面关于uboot的文章中有提到过（eg:zImage）。uboot启动是无条件的，只要代码的位置对，上电就工作，kern
阅读更多...
【秋招笔试】9.07米哈游秋招改编题-三语言题解

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新 🍄 题面描述等均已改编，如果和你笔试题看到的题面描述
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2