2017广西邀请赛复盘：NWAFU全国邀请赛训练赛第八场

邀请赛训练&＃xff0c;只能充当无情的翻译机…还是太菜了&＃xff0c;选取了队友做出来的题来整理

数学、贪心、生成树、前缀后缀和

链接&＃xff1a;NWAFU全国邀请赛复现 - 1&＃xff08;2017广西邀请赛&＃xff09; [Cloned]

A

题目大意&＃xff1a;给出一个数n&＃xff0c;1$\le$n≤1018\le 10^{18}≤1018,求出满足kk≤nk^k\le nkk≤n的正整数k有多少个

思路&＃xff1a;预处理发现161616^{16}1616已经超出了n的范围&＃xff0c;所以预处理1~15的结果&＃xff0c;对每次输入的N二分查找即可

代码

#include
using namespace std;
typedef unsigned long long ull;
ull data[20],N;
int main() {ios::sync_with_stdio(0),cin.tie(0);for(ull i&＃61;1; i<&＃61;16; i&＃43;&＃43;) {ull ans&＃61;1;for(ull j&＃61;0; j<i; j&＃43;&＃43;)ans*&＃61;i;data[i]&＃61;ans;}while(cin >>N) {if(N>&＃61;data[15])cout <<15<<endl;elsecout <<upper_bound(data&＃43;1,data&＃43;16,N)-data-1<<endl;}return 0;
}


E

题目大意&＃xff1a;给出一个有n个数的非负整数序列&＃xff0c;进行q次查询&＃xff0c;每次查询输出去掉一个数之后&＃xff0c;剩余所有数的与、或、异或结果

思路&＃xff1a;利用前缀和后缀和的思路处理即可&＃xff0c;只使用前缀和处理起来会比较麻烦&＃xff0c;再使用后缀和提高效率

代码

#include
using namespace std;
int n,q,Ab[121212],Ob[121212],Xb[121212],Aa[121212],Oa[121212],Xa[121212],data[121212];
int main() {while(~scanf("%d%d",&n,&q)) {for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)scanf("%d",&data[i]);Ab[1]&＃61;Ob[1]&＃61;Xb[1]&＃61;data[1];Aa[n]&＃61;Oa[n]&＃61;Xa[n]&＃61;data[n];for(int i&＃61;2; i<&＃61;n; i&＃43;&＃43;) {//前缀和Ab[i]&＃61;Ab[i-1]&data[i];Ob[i]&＃61;Ob[i-1]|data[i];Xb[i]&＃61;Xb[i-1]^data[i];}for(int i&＃61;n-1; i>&＃61;1; i--) {//后缀和Aa[i]&＃61;Aa[i&＃43;1]&data[i];Oa[i]&＃61;Oa[i&＃43;1]|data[i];Xa[i]&＃61;Xa[i&＃43;1]^data[i];}while(q--) {int t;scanf("%d",&t);if(t!&＃61;1&&t!&＃61;n)//特判一下printf("%d %d %d\n",Ab[t-1]&Aa[t&＃43;1],Ob[t-1]|Oa[t&＃43;1],Xb[t-1]^Xa[t&＃43;1]);else if(t&＃61;&＃61;1)printf("%d %d %d\n",Aa[2],Oa[2],Xa[2]);elseprintf("%d %d %d\n",Ab[n-1],Ob[n-1],Xb[n-1]);}}return 0;
}


F

题目大意&＃xff1a;给定n个点&＃xff0c;m堵墙&＃xff0c;给出每个点左边&＃xff0c;给出每堵墙的首尾、开销&＃xff0c;求出最少拆除多少堵墙&＃xff0c;使得整个坐标系的任何地方都能被访问到&＃xff08;访问面积无穷&＃xff09;&＃xff0c;输出最小开销

思路&＃xff1a;如图&＃xff0c;所需要的便是不存在不能访问到的面积&＃xff08;图中的红色地方无法访问&＃xff09;&＃xff0c;那么&＃xff0c;最后的图就不能存在环&＃xff0c;因此&＃xff0c;考虑一下哪些墙保留之后&＃xff0c;不会形成环&＃xff0c;而花销又要最小&＃xff0c;即求出最大生成树&＃xff0c;然后其他的墙都拆掉即可

代码

#include
using namespace std;
int fa[1212121],n,m;
int seek(int x) {//状态压缩if(fa[x]&＃61;&＃61;x)return x;return fa[x]&＃61;seek(fa[x]);
}
typedef struct node {int x,y,z;bool operator<(node b)const {return z>b.z;}
} node;
node data[1212121];
int main() {while(~scanf("%d%d",&n,&m)) {for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) {int a,b;scanf("%d%d",&a,&b);fa[i]&＃61;i;}int ori&＃61;0,cnt&＃61;0,sum&＃61;0;for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;) {int a,b,c;scanf("%d%d%d",&a,&b,&c);data[i]&＃61; {a,b,c};ori&＃43;&＃61;c;}//记录总共的和sort(data&＃43;1,data&＃43;1&＃43;m);for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;) {//Kruscalint x&＃61;seek(data[i].x),y&＃61;seek(data[i].y);if(x!&＃61;y) {fa[x]&＃61;y;sum&＃43;&＃61;data[i].z;cnt&＃43;&＃43;;if(cnt&＃61;&＃61;n-1)//找到n-1条边即可break;}}printf("%d %d\n",m-cnt,ori-sum);//初始值减去计算值}return 0;
}


G

题目大意&＃xff1a;给出n张牌&＃xff0c;每张牌的点数都是1~n&＃xff0c;定义对子为两个相同的牌&＃xff0c;定义顺子为三个连续数字的牌&＃xff0c;问这n张牌最多能组成对子&＃43;顺子个数多少

思路&＃xff1a;首先&＃xff0c;单从牌数来说&＃xff0c;对子肯定比顺子更好&＃xff0c;因此先把能出对子的都化为对子&＃xff0c;经过这样的操作后&＃xff0c;每种点数的牌只剩下0或1张&＃xff0c;接下来考虑对子的情况&＃xff0c;最好的情况是&＃xff0c;剩下三个连续的单张&＃xff0c;这样就可以直接凑出一个对子了。当剩下连续两张单张&＃xff0c;并且第三个数初始有牌&＃xff0c;就可以凑出一个顺子&＃xff0c;因为即使把第三个数拆开&＃xff0c;少一个对子&＃xff0c;但可以多出一个顺子&＃xff0c;并且第三个数剩下的个数可能为后面多出一个顺子

代码

#include
using namespace std;
int bucket[1212121],a[1212121],cnt[1212121],n;
//桶&＃xff0c;数据&＃xff0c;凑成对子的数量
int main() {while(~scanf("%d",&n)) {memset(bucket,0,sizeof(bucket));memset(cnt,0,sizeof(cnt));//清空for(int i&＃61;0; i<n; i&＃43;&＃43;) {scanf("%d",&a[i]);bucket[a[i]]&＃43;&＃43;;}int ans&＃61;0;for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) {//优先看有没有对子cnt[i]&＃61;bucket[i]/2;bucket[i]%&＃61;2;}for(int i&＃61;1; i<&＃61;n-2; i&＃43;&＃43;)if(bucket[i]&&bucket[i&＃43;1]&&(bucket[i&＃43;2]||cnt[i&＃43;2])) {//判断能不能生成顺子&＃xff0c;连续三个数&＃xff0c;前两个数量为奇时&＃xff0c;此时对换才不亏ans&＃43;&＃43;;bucket[i]--;bucket[i&＃43;1]--;if(bucket[i&＃43;2])bucket[i&＃43;2]--;else {cnt[i&＃43;2]--;bucket[i&＃43;2]&＃43;&＃43;;}}for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)ans&＃43;&＃61;cnt[i];printf("%d\n",ans);}return 0;
}

参考文献

1. HDU6188 (Duizi and Shunzi)[贪心]
2. HDU - 6187 (最大生成树) 最小生成树
3. hdu6187 Destroy Walls&＃xff08;最大生成树&＃xff09;