admin管理员组

文章数量:1794759

重聚

                                        [开天辟地-2008]_梦回2008  

                                                      Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

2008年注定是不平凡的一年。

在这一年，山东理工大学ACM集训队、ACM协会、ACM创新实验室先后成立。
现在我们带你穿越回2008年，带你体验一下学长学姐们第一次参加网络赛时的一道题目。
 

一个正整数N(0＜ｎ＜100），可以写成若干个正整数加数之和，如6可以写成
 
6=1+2+3；
6=2+2+2；
6=2+4；
6=3+3；
6=1+5；
……

其中有一种分解方式获得的加数的乘积是所有分解方式中最大的，比如上面分解中最大的乘积是3×3＝9。

请你设计一种算法，对于任何一个输入的正整数，求出其各种分解中所得到的最大乘积。

Input

输入有多组，每组一行输入一个正整数。以0作为输入的结束。

Output

对应输入的数据，输出多行，输出所求最大分解乘积。 保证答案在64位整数以内 .

Sample Input

6
7
0

Sample Output

9
12

Hint

Source

【重聚--SDUTACM十周年庆典专场赛】改编自网络赛

【分析】:把数字分解成上升数字之和，可利用DFS（深度优先搜索）穷举所有符合要求的形式，以此来求最大的乘积。

正向搜索：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL M;
void DFS(LL n,LL cnt,LL sum,LL x)
{if(n==sum){M=max(M,x);return;}for(LL i=cnt;i<=n;i++){if(sum+i>n){return;}DFS(n,i,sum+i,x*i);}
}
int main()
{LL n;while(scanf("%lld",&n)&&n){M=1;for(LL i=1;i<=n/2;i++){DFS(n,i,i,i);}printf("%lld\n",M);}return 0;
}

反向搜索：

#include <iostream>
#include  <cstdio>
using namespace std;
#define LL long long
LL M;
void DFS(int n,int st,int sum,LL x)
{if(sum==0){M=max(M,x);return;}for(int i=st;i<n;i++){if(sum-i<0)return;DFS(n,i,sum-i,x*i);}
}
int main()
{int n;while(scanf("%d",&n)&&n){M=0;for(int i=1;i<n;i++){DFS(n,i,n-i,(LL)i);  //输入值，开始值，剩余值，当前积；}printf("%lld\n",M);}return 0;
}

反向搜索优化：（TLE）

#include <iostream>
#include  <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL A[110];
LL DFS(int n,LL sum)
{LL M=0;if(sum<5)return sum;if(A[sum])return A[sum];for(LL i=1;i<n;i++){if(sum-i>=0)//return sum;M=max(M,max(DFS(n,sum-i)*i,(sum-i)*i));if(sum==i)break;}return M;
}
int main()
{int n;//freopen("a.txt","w",stdout);memset(A,0,sizeof(A));while(scanf("%d",&n)&&n)// for(n=1;n<=100;n++){LL M=DFS(n,n);  //输入值，开始值，剩余值，当前积；A[n]=M;printf("%lld\n",M);}
//     while(scanf("%d",&n)&&n)
//     {
//         printf("%lld\n",A[n]);
//     }return 0;
}

 继续优化，先按顺序打表在输出：（AC且，0毫秒）

#include <iostream>
#include  <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL A[110];
LL DFS(int n,LL sum)
{LL M=0;if(sum<5)return sum;if(A[sum])return A[sum];for(LL i=1;i<n;i++){if(sum-i>=0)//return sum;M=max(M,max(DFS(n,sum-i)*i,(sum-i)*i));if(sum==i)break;}return M;
}
int main()
{int n;//freopen("a.txt","w",stdout);memset(A,0,sizeof(A));//while(scanf("%d",&n)&&n)for(n=1;n<=100;n++){LL M=DFS(n,n);  //输入值，开始值，剩余值，当前积；A[n]=M;//printf("%lld\n",M);}while(scanf("%d",&n)&&n){printf("%lld\n",A[n]);}return 0;
}

   与其这样（递归）不如写成   递推的形式：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
ll a[110]={0,1,2,3};
int main()
{int n;for(int i=4;i<101;i++){a[i]=i;for(int j=1;j<i;j++){a[i]=max(a[i],a[i-j]*j);}}while(scanf("%d",&n)&&n){printf("%lld\n",a[n]);}return 0;
}

是否可以在小层次的优化：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define LL long longLL A[120]={0,1,2,3};
int main()
{//freopen("b.txt","w",stdout);int n;int tmp;for(int i=4;i<101;i++){tmp=i/2;//A[i]=i;for(int j=2;j<=tmp;j++){//A[i]=max(A[i],A[i-j]*j);A[i]=max(A[i],A[i-j]*A[j]);}}//for(n=1;n<=100;n++)while(scanf("%d",&n)&&n){printf("%lld\n",A[n]);}return 0;
}

 

官方题解：利用均值不等式，可以知道当每一个数都相等的时候，才具有最大值，所以实际上就是将这个数均分，
假设分为n份，那么它们的乘积就是（k/n）^n，其中k为这几个数的和。利用导数知识，可以算出其极
 
值点。
所以当分成尽量多最接近e的3时是最优的，当k%3=1的时候，要把最后的1和一个3合并成4是最优的。
注意用64位整数输出。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f(int n)
{if(n<5)return n;return f(n-3)*3;
}
int main()
{int n;while(scanf("%d",&n)&&n){printf("%lld\n",f(n));}return 0;
}

 

 

                                                         [宁拙毋巧-2009]_圆

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

2009年10月25日是SDUTACM集训队第一次在有组织训练后参加ICPC现场赛。而此时此刻

在南京，有4支SDUT的队伍正在南京航空航天大学代表山东理工大学第十次参加ICPC现场赛。

十年磨一剑，让我们在这儿为在南京比赛的队伍加油，预祝他们能再创佳绩！

 

如图所示，已知第一层半圆的半径为 R，第一层半圆的半径是第二层半圆的直径…… 第 n-1层半圆的半径为第 n 层半圆的直径。

Input

第一行输入一个整数R。

第二行输入一个整数n。

(1 <= R < 2^31, 1 <= 2^n <= R )

Output

输出一个整数，代表第n层的一个半圆中最大矩形的面积 。

Sample Input

8
2

Sample Output

16

Hint

答案保证为整数

Source

【重聚--SDUTACM十周年庆典专场赛】suyu

【分析】:求圆内最大的正方形，此正方形的对角线为圆的 直径，根据逻辑关系很容易得到第i层圆的半径r，r*r即为矩形最大面积。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{LL R,N;while(~scanf("%lld%lld",&R,&N)){R=R>>(N-1);printf("%lld\n",R*R);}return 0;
}

[血战到底-2010]_捏泡泡纸

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

著名的ACM大师Ninaye最近不敲代码了，最近工作压力大，他改为捏泡泡纸来放松心情。由于 bLue 每天上班摸鱼，他被抓过来陪 Ninaye 捏泡泡纸。
已知一张完好的泡泡纸上会有 n 个泡泡，他们约定每次每个人都可以 paji 掉 2 的幂次（1，2，4，8，16，...，2^k​​）个泡泡，并且总是由 Ninaye 先捏，轮流下去直到捏完。他们都想由自己来捏完整张泡泡纸，且他们都足够聪明，总会试图选择最有利于自己的策略。
看他们捏泡泡太无聊了，我想预先知道他们谁能够刚好在最后捏完整张泡泡纸。

Input

多组输入。
每行会输入一个正整数  n 。

( 1 <=  n <= 1e6 )

Output

对于每张泡泡纸，请你告诉我故事的结局。
如果是 Ninaye 最后捏完，输出 "Yes!" （不包括引号，下同）。
如果是 bLue 最后捏完，输出 "No!" 。

Sample Input

4
5
6

Sample Output

Yes!
Yes!
No!

Hint

对于样例 3 ，无论 Ninaye 先捏 1 / 2 / 4 个都改变不了泡泡纸最后被 bLue 捏完。

Source

【重聚--SDUTACM十周年庆典专场赛】axuhongbo

【分析】：其实是一个博弈问题，每部可走2^n,谁走到最后谁获胜。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
bool flag[1<<21];
int A[25];
int main()
{for(int i=0;i<21;i++){flag[(1<<i)]=1;A[i]=1<<i;}for(int i=3;i<1000001;i++){if(!flag[i]){int sum=1;for(int j=0;A[j]<i;j++){sum=sum&&flag[i-A[j]];}flag[i]=!sum;}}int n;while(~scanf("%d",&n)){if(flag[n]){printf("Yes!\n");}else{printf("No!\n");}}return 0;
}

[零的突破-2011]_数发票

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

2011年在第36届ACM-ICPC国际大学生程序设计竞赛亚洲区域赛大连与成都赛站获得铜奖2项，实现了山东理工大学ACM奖牌零的突破。

 

rowanhao 手里拿着一些外出比赛的车票准备到学院报销，学院给了他一定的差旅费报销金额。而 rowanhao 平时是一个十分注重收集车票的人，他的手上有无数张不同面值的发票，现在他想计算最少要多少张发票可以恰好达到报销金额。 rowanhao 忙着整理这些发票，于是把这个任务交给了你，你需要仔细计算否则就拿不到外出的车费了。

Input

输入第一行是一个正整数 T 表示数据组数。接下来是多组数据，每组数据第一行是正整数 n ，分别表示 axuhongbo 有 n 种面值的发票（每种都有无数张），接下来一行有 n 个由空格隔开的正整数 num ，表示这 n 种面值的大小，再下一行是一个正整数 x 表示报销金额(1 <= T <= 50 , 1 <= x <= 1000 , 1 <= n <= 100 , 1 <= num <= 1000 ) 。

Output

对于每一组数据，输出能凑齐报销金额的最少的发票张数，如果不能正好凑齐则输出 -1 。

Sample Input

2
3
1 3 5
11
2
3 5
7

Sample Output

3
-1

Hint

第一组数据中 11= 5 + 5 + 1 = 5 + 3 + 3 ，最少要用 3 张。
第二组数据中无论多少张都凑不齐 7 元，输出 -1。

Source

【重聚--SDUTACM十周年庆典专场赛】axuhongbo

 

【分析】:动态规划问题，到达每一步的最少次数是多少，步长为可以开除的发票。【到达x的次数】=min([到达x的次数],[到达i的次数]+k*步长])  (x=i+k*步长)；

 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int B[1110];
int A[110];//void DFS(int cnt,int pos,int sum,int n,int x)
//{
//    if(flag[sum])
//        return;
//    if(sum==x)
//    {
//        bj=1;
//        M=min(M,cnt);
//        return;
//    }
//    for(int i=pos; i<n; i++)
//    {
//        if(sum+B[i]>x)
//            return;
//        DFS(cnt+1,i,sum+B[i],n,x);
//        if(sum+B[i]==x);
//            break;
//    }
//}
int main()
{int T,n;int x;int tmp;scanf("%d",&T);while(T--){B[0]=0;for(int i=1; i<=1001; i++){B[i]=1010;}scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d",&A[i]);}scanf("%d",&x);for(int i=0; i<n; i++){for(int j=0; j<=x; j++){for(int k=1; (k*A[i]+j)<=x; k++){tmp=k*A[i]+j;B[tmp]=min(B[tmp],B[j]+k);}}}if(B[x]!=1010){printf("%d\n",B[x]);}elseprintf("-1\n");}return 0;
}

 

[舍我其谁-2012]_AC字符串

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

一个字符串的子串表示原字符串中一段连续的部分。例如，字符串"CBC"的子串总共有六个，它们分别是"C"(前一个),"B","C"(后一个),"CB","BC"和"CBC"。但"CC"不是"CBC"的子串，因为两个'C'在原串中不连续。我们认为空串也不是子串。
现给你一个只含有'A'和'C'两种字符的字符串，问它含有相同'A'和'C'的子串有几个。例如，字符串"ACAC"中符合条件的子串有4个。它们分别是"AC"(前一个),"CA","AC"(后一个),"ACAC"。

Input

单组输入。

输入有两行，首先一个 n，代表接下来输入的字符串长度。

第二行输入为给定的字符串。题目保证字符串长度不超过1000，且只包含 'A' 和 'C' 两种字符。

Output

输出为一个数，表示符合条件的子串的个数。

Sample Input

8
AACCAACC

Sample Output

10

Hint

字符串"AACCAACC"中符合条件的子串分别为"AC"(前一个),"CA","AC"(后一个),"AACC" (前一个),"ACCA","CCAA","CAAC","AACC"(后一个),"ACCAAC","AACCAACC"，共10个。
 

Source

【重聚--SDUTACM十周年庆典专场赛】axuhongbo

【分析】：这是一个齿取法，区间连续移动，外层往后加元素，内层分析从头到加上元素后的个数，记录总和求部分，

 

 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
char s[1010];
int A[130];
int B[130];
int main()
{int n;while(~scanf("%d%s",&n,s)){int sum=0;memset(A,0,sizeof(A));for(int i=0;i<n;i++){A[s[i]]++;if(A['A']==A['C'])sum++;B['A']=A['A'];B['C']=A['C'];for(int j=0;j<i;j++){B[s[j]]--;if(B['A']==B['C'])sum++;}}printf("%d\n",sum);}return 0;
}

 

[功不唐捐-2013]_强哥的无敌异或

Time Limit: 3000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

强哥是一个热爱学习的人，他经常去维基百科学习计算机科学。

他在学习位运算时发现了异或的秘密。

就在刚才，强哥认真地学习了一系列位运算符 ，其中按位异或的运算符 xor 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律，即i xor j = j xor i。

他发现，按位异或可以理解成被运算的数字的二进制位对应位如果相同，则结果的该位置为0，否则为1，例如1(01) xor 2(10) = 3(11)。

他还发现，按位异或可以理解成数字的每个二进制位进行了不进位的加法，例如3(11) xor 3(11) = 0(00)。

 

现在强哥给你一个长度为n的数列 , 然后给出q次询问[l , r] , 每次询问请你输出 [l, r] 之间出现次数为奇数次的数字的异或和 。

注: 异或即按位异或, C语言运算符号为 ^ ;  

Input

给出T组数据 。
每组先给出一个 n 。
然后给出 n 个数字 , 每个数字小于等于 100000 ;
然后给出 q , 接下来 q 行, 每行一个 l , r 。

（n <= 100000，T <= 5，q <= 100000，1 <= l <= r <= n ）

 

Output

对于每个输入，输出一行，包含一个整数，即为每次询问的答案。

Sample Input

1
3
1 2 3
2
1 3
2 3

Sample Output

0
1

Hint

Source

【重聚--SDUTACM十周年庆典专场赛】Ransln

【分析】：提示，两个相同的数异或为零，零与任何数异或为任何数。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int A[101000];
int B[101000];
int main()
{int t;int n;int q,l,r;scanf("%d",&t);while(t--){scanf("%d",&n);B[0]=0;for(int i=0;i<n;i++){scanf("%d",&A[i]);B[i+1]=B[i]^A[i];}scanf("%d",&q);while(q--){scanf("%d%d",&l,&r);printf("%d\n",B[l-1]^B[r]);}}return 0;
}

 

[渐入佳境-2014]_Casithy的饮料

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

2014年SDUTACM集训队在第39届ACM-ICPC国际大学生程序设计竞赛亚洲区域赛牡丹江与广州赛站获得银奖2项，实现了山东理工大学银牌零的突破。

Casithy 在超市买了 n 瓶饮料，他们的品牌分别为a1,a2,a3 ... ai ... an.
但他不小心把开盖的工具弄丢了,所以他只能利用饮料瓶来开盖 。
已知第i个瓶子的品牌为 ai , 且其能打开 bi 品牌的瓶子 。
问有几瓶饮料 Casithy 无法喝到 。
被用于打开饮料瓶的瓶子不一定需要被打开 。
一个瓶子不能打开其本身 。

Input

单组输入。
第一行一个整数 n , 表示饮料的瓶数 。
接下来n行 , 每行两个整数a[i] ，b[i]，分别代表他所拥有的第 i 瓶饮料的品牌和第 i 瓶饮料能打开的饮料品牌。

（ 1 ≤ n ≤ 100，1 ≤ ai , bi ≤ 1000 ）

Output

输出一行一个整数 , 表示 Casithy 无法喝到的饮料瓶数。

Sample Input

4
1 1
2 3
3 2
3 3

Sample Output

1

Hint

第一个瓶子不能被任何瓶子打开，第二个瓶子能被第三个瓶子打开，第三个瓶子能被第二个或者第四个瓶子打开，第四个瓶子能被第二个瓶子打开

Source

【重聚--SDUTACM十周年庆典专场赛】axuhongbo

【分析】：注意1.不要加重，2.自己不能开自己

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int A[1010];
int B[1010];
int num[1010];
int flag[1010];
int main()
{int n;while(~scanf("%d",&n)){memset(num,0,sizeof(num));memset(flag,0,sizeof(flag));for(int i=0;i<n;i++){scanf("%d %d",&A[i],&B[i]);num[A[i]]++;}int sum=0;for(int i=0;i<n;i++){if(A[i]!=B[i]&&!flag[B[i]]){sum+=num[B[i]];flag[B[i]]=1;}}printf("%d\n",n-sum);}return 0;
}

 

[破茧成蝶-2015]_理工长廊

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

今天真的是开心的一天，又可以品尝到理工大饭菜的味道了。

 

mle 和 axuhongbo 来到了长廊入口，发现同时有 n 个人进去。

axuhongbo 脑洞大开，想到了一个问题，问了一波 mle.

如果长廊有 m 家店铺编号从 1 到 m，每个人在各个店铺选择进去吃饭的概率是一样的，保证每个人不互相认识（也就是不相互影响）。

输出有人进第 pos家店铺的概率，题目保证每一个人都会进入一家店铺吃饭。

mle 一听到题目，这不是圣昭题嘛，一般圣昭题我都不会做。

mle 只能寻求各位聪明的小伙伴了。

Input

单组输入，输入包括一行。

依次输入三个整数n , m , pos 。

（5 <= n <=50 , 5 <= m <=50 , 1 <= pos <= n）

Output

输出一行，包含一个实数（保留两位小数），代表有人进第 pos家店铺的概率。

Sample Input

6 6 6

Sample Output

0.67

Hint

Source

【重聚--SDUTACM十周年庆典专场赛】笑对这个世界的志贵

【分析】；这道题考察反向思维吧，去第pos家的概率为= 1-不去这家的概率；

n个人不去这家的概率=（1减去 每个去这家的概率的n次方;

概率问题，古典概型，和哪家没关系

#include <iostream>
#include <bits/stdc++.h>
using namespace std;int main()
{int n,m,pos;while(~scanf("%d%d%d",&n,&m,&pos)){double tmp=1.0-1.0/m;double ans=1.0;for(int i=0;i<n;i++){ans*=tmp;}printf("%.2f\n",1-ans);}return 0;
}

 

 

本文标签： 重聚