1.ADV-150 周期字串
时间限制：1.0s 内存限制：256.0MB
#include<iostream>
#include<string>
using namespace std;
int main(){
string str,s1,s2,ans;
int result;
while(cin>>str){
int len=str.length();
ans=str;
for(int i=1;i<=len;i++){
if(len%i!=0)
continue;
s1=str.substr(0,i);//获得字符串str中 从第0位开始的长度为i的字符串,默认时的长度为从开始位置到尾
int flag=1;
for(int j=i;j<len;j+=i){
s2=str.substr(j,i);
if(s1!=s2){
flag=0;break;
}
}
if(flag){
result=i;break;
}
}
cout<<result<<endl;
}
return 0;
}
2.ADV-155
问题描述
第一分钟，上帝说：要有题。于是就有了L，Y，M，C
第二分钟，LYC说：要有向量。于是就有了长度为n写满随机整数的向量
第三分钟，YUHCH说：要有查询。于是就有了Q个查询，查询向量的一段区间内元素的最小值
第四分钟，MZC说：要有限。于是就有了数据范围
第五分钟，CS说：要有做题的。说完众神一哄而散，留你来收拾此题
输入格式
第一行两个正整数n和Q，表示向量长度和查询个数
接下来一行n个整数，依次对应向量中元素：a[0]，a1，…，a[n-1]
接下来Q行，每行两个正整数lo，hi，表示查询区间[lo, hi]中的最小值，即min(a[lo],a[lo+1],…,a[hi])。
输出格式
共Q行，依次对应每个查询的结果，即向量在对应查询区间中的最小值。
样例输入
7 4
1 -1 -4 8 1 2 -7
0 0
1 3
4 5
0 6
样例输出
1
-4
1
-7
样例说明
第一个查询[0,0]表示求min{a[0]}=min{1}=1
第二个查询[1,3]表示求min{a1,a2,a[3]}=min{-1,-4,8}=-4
第三个查询[4,5]表示求min{a[4],a[5]}=min{1,2}=1
第四个查询[0,6]表示查询整个向量，求min{a[0..6]}=min{1,-1,-4,8,1,2,-7}=-7
数据规模和约定
1<=n<=1984，1<=Q<=1988，向量中随机整数的绝对值不超过1,000
#include<stdio.h>
int c[2000];
int min(int a,int b,int c[])
{
int i,min = c[a];
for(i = a;i<=b;i++)
if(c[i]<min)
min = c[i];
return min;
}
int main()
{
int n,Q,i,lo,hi;
scanf("%d%d",&n,&Q);
for(i = 0;i<n;i++)
scanf("%d",&c[i]);
for(i = 0;i<Q;i++)
{
scanf("%d%d",&lo,&hi);
printf("%d\n",min(lo,hi,c));
}
return 0;
}
3.ADV-164(DP)
问题描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天
对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。
今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，
下表就是一些主件与附件的例子：
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。
附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，
分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。
他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j_1，j_2，……，j_k，则所求的总和为：
v[j_1]w[j_1]+v[j_2]w[j_2]+ …+v[j_k]w[j_k]。（其中为乘号)
请你帮助金明设计一个满足要求的购物单。
输入格式
输入文件budget.in 的第1行，为两个正整数，用一个空格隔开：N m（其中N（<32000）表示总钱数，
m（<60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，
每行有3个非负整数 v p q（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），
q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）
输出格式
输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）
样例输入
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
样例输出
2200
【思路】
对于经典的背包问题，我们都知道每个物品有两种决策，即放入或不放入。
但这个题多了一些限制条件，所以每个物品的决策不止两个了。但由于题目里有这句话“每个主件可以有0个、1个或2个附件”，
所以可以这样做：
如果第i号物品为附件，就直接忽视了它。
如果第i号物品为主件，那么就有这么几种决策：不放入它；仅放入它；仅放入它和它的第一个附件；
仅放入它和它的第二个附件；放入它和它的所有附件。
由此得出算法。
#include<stdio.h>
int v[70]; // 价格
int p[70]; // 重要度
int q[70]; // 主/附件
int f[50000];
int max(int a,int b)
{ return a > b ? a : b; }
int main()
{
int n,m;
int i,j,k;
int t1,t2;
scanf("%d%d",&n,&m);
for(i = 1; i <= m; i++)
{
scanf("%d%d%d",&v[i],&p[i],&q[i]);
}
for(i = 1; i <= m; i++)
{
t1=0;
t2=0;
if(q[i] == 0) //主件
{
for(k = i+1;k <= m; k++) //附件1
if(q[k] == i)
{
t1 = k; //保存附件1的位置
break;
}
for(k = t1+1;k <= m; k++)//附件2
if(q[k] == i )
{
t2 = k; //保存附件2的位置
break;
}
for(j = n; j >= v[i]; j--)
{
f[j] = max(f[j-v[i]]+v[i]*p[i],f[j]); //取主件
if(( j-v[i]-v[t1])>=0 )//取附件1
f[j] = max(f[j-v[i]-v[t1]]+v[i]*p[i]+v[t1]*p[t1],f[j]);
if( j-v[i]-v[t2]>=0 )//取附件2
f[j] = max(f[j-v[i]-v[t2]]+v[i]*p[i]+v[t2]*p[t2],f[j]);
if((j-v[i]-v[t1]-v[t2])>=0) //附件1,2都取
f[j] = max(f[j-v[i]-v[t1]-v[t2]]+v[i]*p[i]+v[t1]*p[t1]+v[t2]*p[t2],f[j]);
}
}
}
printf("%d\n",f[n]);
return 0;
}