I题
总感觉n^3会超时，一直在想如何优化，后来翻了翻题解，发现其实并不需要n^2,只要加一个小小的剪枝就可以了。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,m;
long long f[1010][1010],a[1010],s[1010];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof(f));
for(int i = 1; i <= n; ++i)
{
scanf("%lld",&a[i]);
s[i] = s[i - 1] + a[i];
}
f[0][0] = 0;
for(int i = 1;i <= n; ++i)
for(int j = 1;j <= min(m,i); ++j)
{
for(int k = i - 1;k >= 0; --k)
{
f[i][j] = min(f[i][j],f[k][j - 1] + (s[i] - s[k]) * (s[i] - s[k]));
if((s[i] - s[k]) * (s[i] - s[k]) > f[i][j]) break;
}
}
printf("%lld\n",f[n][m]);
}
return 0;
}
补一补昨天晚上的题。
E题
"Ever Dream" played by Nightwish is my favorite metal music. The lyric (see Sample Input) of this song is much more like a poem. Every people may have their own interpretation for this song depending on their own experience in the past. For me, it is a song about pure and unrequited love filled with innocence, willingness and happiness. I believe most people used to have or still have a long story with someone special or something special. However, perhaps fatefully, life is totally a joke for us. One day, the story ended and became a dream in the long night that would never come true. The song touches my heart because it reminds me the dream I ever had and the one I ever loved.
Today I recommend this song to my friends and hope that you can follow your heart. I also designed a simple algorithm to express the meaning of a song by several key words. There are only 3 steps in this algorithm, which are described below:
Step 1: Extract all different words from the song and counts the occurrences of each word. A word only consists of English letters and it is case-insensitive.
Step 2: Divide the words into different groups according to their frequencies (i.e. the number of times a word occurs). Words with the same frequency belong to the same group.
Step 3: For each group, output the word with the longest length. If there is a tie, sort these words (not including the words with shorter length) in alphabetical order and output the penultimate one. Here "penultimate" means the second to the last. The word with higher frequency should be output first and you don't need to output the word that just occurs once in the song.
Now given the lyric of a song, please output its key words by implementing the algorithm above.
Input
The first line of input is an integer T (T < 50) indicating the number of test cases. For each case, first there is a line containing the number n (n < 50) indicating that there are n lines of words for the song. The following n lines contain the lyric of the song. An empty line is also counted as a single line. Any ASCII code can occur in the lyric. There will be at most 100 characters in a single line.
Output
For each case, output the key words in a single line. Words should be in lower-case and separated by a space. If there is no key word, just output an empty line.
Sample Input
1
29
Ever felt away with me
Just once that all I need
Entwined in finding you one day
Ever felt away without me
My love, it lies so deep
Ever dream of me
Would you do it with me
Heal the scars and change the stars
Would you do it for me
Turn loose the heaven within
I'd take you away
Castaway on a lonely day
Bosom for a teary cheek
My song can but borrow your grace
Come out, come out wherever you are
So lost in your sea
Give in, give in for my touch
For my taste for my lust
Your beauty cascaded on me
In this white night fantasy
"All I ever craved were the two dreams I shared with you.
One I now have, will the other one ever dream remain.
For yours I truly wish to be."
Sample Output
for ever with drea
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
string s;
map<string,int>q;
vector<string>v[5100];
int a[5100],tot,n,T;
bool cmp(int x,int y)
{
return x > y;
}
bool cmp1(string x,string y)
{
if(x.size() == y.size()) return x < y;
return x.size() > y.size();
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
q.clear();
getchar();
for(int i = 0;i <= 5000; ++i) v[i].clear();
for(int i = 0;i < n; ++i)
{
getline(cin,s);
int len = s.size();
if(!len)continue;
string tmp = "";
for(int i = 0;i < len; ++i)
{
if(isalpha(s[i]))
tmp += tolower(s[i]);
else
{
if(tmp != "") q[tmp]++;
tmp = "";
}
}
if(tmp != "") q[tmp]++;
}
tot = -1;
map<string,int>::iterator it;
for(it = q.begin();it != q.end(); it++)
{
if(it->second <= 1) continue;
if(!v[it->second].size()) a[++tot] = it->second;
v[it->second].push_back(it->first);
}
sort(a,a + tot + 1,cmp);
bool f = 0;
for(int i = 0;i <= tot; ++i)
{
sort(v[a[i]].begin(),v[a[i]].end(),cmp1);
if(f) cout<<' '; f = 1;
int p = 1;
while(v[a[i]].size() > p && v[a[i]][p].size() == v[a[i]][0].size()) p++;
p--;
if(p >= 1) cout<<v[a[i]][p - 1];
else cout<<v[a[i]][0];
}
cout<<'\n';
}
return 0;
}
终于明白Segmentation Fault的错误大致是如何造成的了。大部分是因为STL里的数据类型访问超限
比如说队列在没判空的情况下直接取队首元素，在这个题里面则是因为vector数组访问时访问到了大于v[i].size()的元素报错。
其实这个题也不是很难，因为字符串处理的题做得少，存取的时候卡住了好多次，所以比赛时花了很长时间也没做对，还是太菜了555 应该做几道字符串处理的题里练练手的QAQ，安排上啦。。
H题（01背包 记录路径）
ennn，这个题大意：
在赛场上，每个题都有一个气球，给出每个题的时间以及得到的气球对妹子的吸引力，求出最大的吸引力，保证吸引力最大的情况下，做题数最多，罚时最少。
做的时候考虑到了这题的两个关键：（1）有两个价值（吸引力和题数） （2）需要记录路径（计算时长）
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,T,ans,tot;
int w[1010],v[1010],f[1010],a[1010],p[1010][1010];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
memset(p,0,sizeof(p));
for(int i = 1;i <= m; ++i) scanf("%d",&w[i]);
for(int i = 1;i <= m; ++i) scanf("%d",&v[i]);
for(int i = 1;i <= m; ++i)
{
for(int j = n; j >= w[i]; --j)
if(f[j] < f[j - w[i]] + v[i])
{
f[j] = f[j - w[i]] + v[i];
p[i][j] = 1;
}
}
int j = n;
tot = -1;
for(int i = m; i >= 0; --i)
if(p[i][j])
{
a[++tot] = w[i];
j -= w[i];
}
sort(a,a + tot + 1);
ans = 0;
for(int i = 0;i <= tot; ++i)
{
if(i) a[i] += a[i - 1];
ans += a[i];
}
printf("%d %d %d\n",f[n],tot + 1,ans);
}
return 0;
}
京公网安备 11010502036488号