@hsxrr
2016-12-06T13:37:45.000000Z
字数 9356
阅读 1111
题解 2016/12/04
A - Design Tutorial: Learn from Math
给你一个数n，（12<=n<=1e6）,求两个素数a,b; 使得a+b=n
如果有多组a,b,只需要输出其中一组即可.
方法1：可以打印质数表（1-1e6），从4开始判断，如果n-4是素数，那么输入4，n-4,否则判断下一个素数6…..直到符合题意为止
方法2：其实k = 4,6,8,9中必有一个数能够满足n-k是素数
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define N 1000007
int n;
int a[10] = {4,6,8,9,10};
bool what(int x){
for(int i = 2 ; i <= sqrt(x) ; i++){
if( x % i == 0 ) return true;
}
return false;
}
int main(){
while( scanf("%d",&n) != EOF ){
for(int i = 0 ; i < 5 ; i++){
if( what(n-a[i]) ){
printf("%d %d\n",a[i],n-a[i]);
break;
}
}
}
return 0;
}
B - Design Tutorial: Learn from Life
给你n个人，电梯最多能够承载k个人
然后给你n个人分别想要去的楼层
电梯从a楼到达b楼需要|a-b|秒钟，乘客进出电梯的所需要的时间为0
现在求出电梯运完这些人然后回到一楼需要的最短时间
贪心，将所有人分组，分成k人一组,其中第一组取完后保证剩下的人是k的倍数即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2048
int n,k,ans;
int f[N];
int main(){
while( scanf("%d%d",&n,&k) != EOF ){
ans = 0;
for(int i = 0 ; i < n ; i++){
scanf("%d",&f[i]);
}
sort(f,f+n);
int have = 0 , last = n;
for(int i = 0 ; i < n ; i++){
have++;
last--;
if( have == k && last > k ){ans += 2*(f[i]-1);have = 0;
}
else if( have <= k && last % k == 0 ){ans += 2*(f[i]-1);have = 0;
}
else if( last < k ){
ans += 2*(f[n-1]-1);
break;
}
}
printf("%d\n",ans);
}
return 0;
}
C - Design Tutorial: Make It Nondeterministic
给n个人的名和姓，然后给一个排序方案，
判断这个排序方案是否为字典序
姓和名可以交换（可以不全部交换）
既然姓与名可以随意交换，那么只要把每个人名字中字典序小的作为优先选择的对象，接着按照给定顺序排序，如果优先选择的对象不能满足，那就交换，在判断字典序大的是否能选择，如果能，标记这个字符串，往下判断，否组结束判断，输出no
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100007
struct node{
string a,b;
bool pdf;
};
int n;
node s[N];
int cf[N];
bool flag;
int main(){
while( scanf("%d",&n) != EOF ){
flag = true;
for(int i = 1 ; i <= n ; i++){
cin>>s[i].a>>s[i].b;
if( s[i].a > s[i].b ){
string c;
c = s[i].a;
s[i].a = s[i].b;
s[i].b = c;
}
s[i].pdf = false;
}
for(int i = 1 ; i <= n ; i++){
scanf("%d",cf+i);
}
for(int i = 2 ; i <= n && flag ; i++){
if( s[cf[i-1]].pdf ){
if( s[cf[i]].a <= s[cf[i-1]].b ){
if( s[cf[i]].b > s[cf[i-1]].b ){
s[cf[i]].pdf = true;
}else{
flag = false;
}
}
}else{
if( s[cf[i]].a <= s[cf[i-1]].a ){
if( s[cf[i]].b > s[cf[i-1]].a ){
s[cf[i]].pdf = true;
}else{
flag = false;
}
}
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
给你6根长短不一的线，然呢判断这6根线能变成大象还是熊
大象和熊的四肢是等长的，
大象的头和身体一样长，
熊的头比身体短，
头和脚，身体和脚的长短是任意的（你确定！！！）
查询这6个数是否存在4个数相等
如果存在在判断剩下两边是否等长即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int p[6];
int main(){
while( scanf("%d",p) != EOF ){
for(int i = 1 ; i < 6 ; i++){
scanf("%d",p+i);
}
sort( p,p+6 );
if( p[1] == p[2] && p[2] == p[3] && p[3] == p[4] ){
if( p[0] == p[5] ) printf("Elephant");
else printf("Bear");
}else if( p[0] == p[1] && p[2] == p[1] && p[2] == p[3] ){
if( p[4] == p[5] ) printf("Elephant");
else printf("Bear");
}else if( p[4] == p[5] && p[2] == p[4] && p[2] == p[3] ){
if( p[1] == p[0] ) printf("Elephant");
else printf("Bear");
}else{
printf("Alien");
}
printf("\n");
}
return 0;
}
有n个问题，第i个问题的难度是hi
要先解决简单题在攻难题
相同难度的问题谁先解决谁后解决都可以
判断是否能够用超过3种符合题意的解题顺序
如果能给出任意3中解题顺序
对题目难度进行排序，然后判断是否存在难度相等的情况，如果存在标记++
判断标志如果大于2那就能提供3种方法
3种方法先按照原来的顺序输出一种
第二种交换第一次重复出现的位置，然后输出
第三种交换第二次重复出现的位置，然后输出
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2048
int n,f[N],ans2,u3ans;
struct node{
int wj;
int val;
int swj;
};
node p[N];
bool cmp( node a , node b ){
if( a.val == b.val )
return a.wj < b.wj;
return a.val < b.val;
}
void solve2(){
int i;
for( i = 1 ; i < n ; i++ ){
if( p[i].val == p[i+1].val ){
int temp = p[i].wj;
p[i].wj = p[i+1].wj;
p[i+1].wj = temp;
break;
}
}
i++;
printf("%d",p[1].wj);
for( int k = 2 ; k <= n ; k++ ){
printf(" %d",p[k].wj);
}
printf("\n");
for( ; i < n ; i++ ){
if( p[i].val == p[i+1].val ){
int temp = p[i].wj;
p[i].wj = p[i+1].wj;
p[i+1].wj = temp;
break;
}
}
printf("%d",p[1].wj);
for( int k = 2 ; k <= n ; k++ ){
printf(" %d",p[k].wj);
}
printf("\n");
}
int main(){
while( scanf("%d",&n) != EOF ){
memset(f,0,sizeof(f));
ans2 = 0;u3ans = 0;
for(int i = 1 ; i <= n ; i++){
scanf("%d",&p[i].val);
p[i].wj = i;
if( f[p[i].val] == 0 ){
f[p[i].val] = i;
}else{
p[i].swj = f[p[i].val];
ans2++;
}
}
sort(p+1,p+n+1,cmp);
if( ans2 > 1 ){
printf("YES\n");
printf("%d",p[1].wj);
for( int k = 2 ; k <= n ; k++ ){
printf(" %d",p[k].wj);
}
printf("\n");
solve2();
}else printf("NO\n");
}
return 0;
}
给您n张纸牌，然后让您搭建一个房子，其中，2张纸牌可以搭成一个帐篷，就像这样 /\ ，但是如果想要不止一层楼必须保证您房子的高一层要比低一层的帐篷数少就可以了
但是无论是高一层还是低一层
您都需要保证每层的每相邻两个帐篷顶之间有且只有一张纸牌连接
像这样
/\▔/\
/\▔/\▔/\▔/\▔/\
现在问您，有多少种层数的房子能被修建
对于第i层，只要n能满足
n-2i 是3的倍数
并且 (n-2i)/3 不小于 0 到 i-1的和
就可以盖第i层，然后暴力便利所有可能的情况即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 1010
LL n,ans,now,nnow;
void solve(){
LL sum = 0;
ans = 0;
nnow = n-2;
for( int i = 1 ; 2*i+3*sum <= n ; ){
if( nnow % 3 == 0 && nnow/3 >= sum ){
ans++;
}
sum += i++;
nnow -= 2;
}
}
int main(){
while( scanf("%lld",&n) != EOF ){
solve();
printf("%lld\n",ans);
}
return 0;
}
大象用单位立方体制造了一排墙，墙的长度为n，宽度为1，在长度方向上第i个单位长度的墙高度为bi
熊也用单位立方体制造了一排塔，塔的长度为1，宽度为1，在长度方向上第i个单位长度的墙高度为ai
现在大象想要知道熊制造的塔，有多少个部分像大象造的塔其中，大象能够任意改变自己墙下面的地面高度（可以降低，可以升高，且不改变熊造的墙下方的地面高）,其中只要大象造的墙上方与熊造的墙的对应长度上方完全重合就认为这个部分是相同的
因为上方一样，下方高度可以任意改，那么只要相邻两块的差值相同即可，匹配的时候就匹配对于任意的k属于2-w,恒有
A(i+k) – A(i+k-1) == B(k) – B(k-1)即可
找到满足所有条件的i即可
暴力匹配会T，这里用KMP优化时间复杂度，将其降到o(n+m)
同时要注意，匹配的是相邻两项的差值那就要讨论没有相邻项的情况
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
#define N 200007
LL p[N],c[N];
LL t[N],pj[N],ans;
LL nextt[N];
int n,w;
void getnext(){
int j,k;
memset(nextt,0,sizeof(nextt));
nextt[1] = 0;
j = 1;
k = 0;
while( j < w ){
if( k == 0 || t[j] == t[k] )
nextt[++j] = ++k;
else
k = nextt[k];
}
}
void kmp(){
ans = 0;
getnext();
for( int i = 1 , k = 1; n-i >= w-k ; ){
if( k == 0 || pj[i] == t[k] ){
i++;k++;
}else{
k = nextt[k];
if( k == 0 ){
i++;
k = 1;
}
}
if( k == w){
ans++;
k = nextt[w-1];
i--;
}
//printf("now is i = %d\n",i);
}
}
int main(){
//freopen( "datain.txt","r",stdin );
p[0] = 0;
while( scanf("%d%d",&n,&w) != EOF ){
for(int i = 1 ; i <= n ; i++){
scanf("%lld",p+i);
pj[i-1] = p[i] - p[i-1];
//sump[i] = sump[i-1] + p[i];
}
scanf("%lld",c+1);
for(int i = 2 ; i <= w ; i++){
scanf("%lld",c+i);
t[i-1] = c[i] - c[i-1];
}
if( n == 1 ){
if( w == 1 ) ans = 1;
else ans = 0;
}else if( w == 1 ){
ans = n;
}else
kmp();
printf("%lld\n",ans);
}
return 0;
}
有两个人想要找一间教室在一起，现在找到n间教室，每间教室都有pi个人在里面，其中教室容量为qi个人，问他们要在一起有多少教室可以选择
找qi-pi >= 2 的教室有多少间就可以了
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,ans,p,q;
int main(){
while( scanf("%d",&n) != EOF ){
ans = 0;
for(int i = 0 ; i < n ; i++){
scanf("%d%d",&p,&q);
if( q-p >= 2 ) ans++;
}
printf("%d\n",ans);
}
return 0;
}
一个战争类小游戏，里面有m个npc，n种士兵
其中npc编号为1到m，士兵编号为0到(n-1)
玩家编号为m+1
每个npc与玩家都拥有军队，其中军队有一个十进制整数，十进制整数转换成一个n位的二进制数以后，每一位二进制数表示是否拥有这类士兵，1表示拥有，0表示没有
如果玩家与npc，或者玩家与玩家之间拥有的士兵种类数目少于k种，表示这俩个人可以成为盟友现在编号为m的玩家想知道自己可以有多少盟友.
让玩家与每一位npc的军队按位异或，异或后的值对一个2^I (i从0-n)按位与检测不同的士兵种类有多少种，再判断是否能成为盟友即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 1010
int n,m,k,ans;
LL p[N],flag,pdf;
void solve(){
int t = 0;
LL f = 1;
for( f = 1 ; f <= flag ; f *= 2 ){
if( f & flag ){
t++;
}
}
if( t<=k ) ans++;
}
int main(){
while( scanf("%d%d%d",&n,&m,&k) != EOF ){
ans = 0;
for(int i = 1 ; i <= m ; i++){
scanf("%lld",p+i);
}
scanf("%lld",&pdf);
for( int i = 1 ; i <= m ; i++ ){
flag = pdf^p[i];
//printf("flag = %lld\n",flag);
solve();
}
printf("%d\n",ans);
}
return 0;
}
给你序列p1,p2,p3,...,pn
然呢选出k个连续且长度为l的区间，使得选出的区间中所有值之和最大
动态规划
dp[当前选中序列中的前i项][当前已选中k个区间]
则dp[i][k] = max(dp[i-1][k] , dp[i-1][k-m] + m-k的区间和)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 5050
LL dp[N][N],sum[N],p[N];
int n,m,k;
void solve(){
memset(dp,0,sizeof(dp));
for( int i = m ; i <= n ; i++ ){
for( int j = 1 ; j <= k ; j++ ){
dp[i][j] = max( dp[i-1][j] , dp[i-m][j-1] + sum[i] );
}
}
}
int main(){
p[0] = 0;
while( scanf("%d%d%d",&n,&m,&k) != EOF ){
for( int i = 1 ; i <= n ; i++ ){
scanf("%lld",p+i);
p[i] += p[i-1];
if( i >= m ){
sum[i] = p[i] - p[i-m];
}else{
sum[i] = 0;
}
}
solve();
printf("%lld\n",dp[n][k]);
}
return 0;
}
一个人要坐地铁n次
票价一 ： 一次 a 元
票价二 ： m次 b元
求最小消费
简单的贪心问题，如果单程票比多程票鬼贵，那么每次贪心多程票，最后一次要特殊处理
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,m,a,b,ans;
int main(){
while( scanf("%d%d%d%d",&n,&m,&a,&b) != EOF ){
ans = 0;
if( a * m <= b ){
ans = a * n;
}else{
int t = n/m;
ans = t * b;
t = n%m;
if( t * a <= b ){
ans += t*a;
}else{
ans += b;
}
}
printf("%d\n",ans);
}
return 0;
}
求min(i*j) >= s*6
其中 i >= a , j >= b
因为没有能够直接判断满足条件的i,j，所以只能暴力枚举所有情况，记录所有情况的面积最小值即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
LL s,a,b,ans;
int main(){
while( scanf("%lld%lld%lld",&s,&a,&b) != EOF ){
s *= 6;
ans = 999999999999;
if( a*b >= s ){
printf("%lld\n%lld %lld\n",a*b,a,b);
}else{
LL aup = a, bup = b;
LL z = max(aup,bup);
for( LL i = min(aup,bup) ; i < s ; i++ ){
LL k = s/i;
if( i* k < s ) k++;
if( i > k ) break;
if( k < z ) k = z;
if( i*k < ans ){
ans = i*k;
if( aup <= bup ){
a = i;
b = k;
}else{
a = k;
b = i;
}
}
}
printf("%lld\n%lld %lld\n",ans,a,b);
}
}
return 0;
}
对于给定序列a1,a2,a3,....,an
取l,k满足
1 < l < k < n
a1,a2,...,al-1 与 al,al+1,al+2,...,ak 与 ak+1,ak+2,...an
三段之和相等
问有多少组l,k能够满足条件
在所有和能够被3整除的前提下上述条件才有意义
在有意义的情况下，每便利到一次（设总和为sum），2sum/3就可以以此点作为一次划分依据，一共有之前便利到了sum/3的数目，就能有多少种不同的分法，把这些划分依据的所有情况加入ans即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 500007
LL p[N],sum[N];
LL n,ans;
void find(LL a){
LL b = a*2,fa = 0,fb = 0;
for(int i = 1 ; i < n ; i++){
if( sum[i] == b ){
fb += fa;
}
if( sum[i] == a ){
fa++;
}
}
ans = fb;
}
int main(){
sum[0] = 0;
while( scanf("%d",&n) != EOF ){
for(int i = 1 ; i <= n ; i++){
cin>>p[i];
sum[i] = sum[i-1]+p[i];
}
if( sum[n] % 3 == 0 ){
find(sum[n]/3);
cout<<ans<<endl;
}
else
printf("0\n");
}
return 0;
}