40 条题解
-
3东大微雕 LV 8 @ 2015-02-08 18:09:39
这道题关键在于找到规律:
XXXX XXYY XYYX XYXY
四种情况包含了全部的2对数字情况。
问题转化为:给你一个数字串,求每两对相同的数字是一组,求一共有多少组数字(组与组之间元素不重叠)。
#include<iostream>
using namespace std;
int a[4007];
int size;
int main(){
freopen("in.txt", "r", stdin);
cin >> size;
int i;
for (i = 0; i < size; i++){
cin >> a[i];
}
int from = 0;
int temp = 0;
int ans = 0;
int j;
for (i = 0; i < size; i++){
for (j = from; j < i; j++){
if (a[i] == a[j]){
temp++;
a[i] = a[j] = -1;
break;
}
}
if (temp == 2){
temp = 0; ans++; from = i;
}
}
cout << ans << endl;
return 0;
} -
22017-08-19 13:27:32@
#include <cstdio> int main() { int n, a[10005], r = 0, c = 0, f = 0; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &a[i]); #ifdef LOCAL puts("==="); #endif for(int i = 0; i < n; i++) { for(int j = f; j < i; j++) { if(a[i] == a[j]) { c++; #ifdef LOCAL printf("a[%d] == a[%d]: %d\n", i, j, a[i]); for(int o = 0; o < n; o++) printf("%d ", a[o]); printf("\n"); #endif a[i] = a[j] = 0; break; } } if(c == 2) r++, c = 0, f = i; } printf("%d", r); return 0; }
-
02020-11-19 20:47:25@
#include <bits/stdc++.h>
using namespace std;
int num[4001];//源数据
int word[10001];//可能出现的整数
int two=0,four=0;
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>num[i];
int sum=0;
for(int i=0;i<n;i++)
{
word[num[i]]++;
if(word[num[i]]==2)two++;//某一个数出现两次
if(word[num[i]]==4)four++;//或某一个出现了四次
if(two==2)//有两个数出现两次
{
sum++;
memset(word,0,sizeof(word));//前面的数和后面的没关系
two=0;
four=0;
}
else if(four)//或有一个数出现四次
{
sum++;
memset(word,0,sizeof(word));//前面的数和后面的没关系
two=0;
four=0;
}
}
cout<<sum<<endl;
return 0;
} -
02018-09-24 16:52:23@
大概就是骗分小方式,来自大佬
#include<iostream>
using namespace std;
int from=0,sum=0,hh=0;
int a[10001];
int n,i,j;
int main()
{
cin>>n;
for(i=0;i<n;i++){cin>>a[i];}
for(i=0;i<n;i++)
{
for(j=from;j<i;j++)if(a[i]==a[j])
{
hh++;
a[i]=0;
a[j]=0;
break;
}
if(hh==2)
{
hh=0;
sum++;
from=i;
}
}
cout<<sum;
return 0;
} -
02018-05-20 21:26:52@
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int n;
cin>>n;
int a;
int lia[10001]={0},sum=0,zan=0;
for(int i=1;i<=n;i++)
{
cin>>a;
lia[a]=lia[a]+1;
if(lia[a]==2)
zan=zan+1;
if(zan==2)
{
sum=sum+1,zan=0,memset(lia,0,sizeof(lia));
}
if(lia[a]==4)
{
sum=sum+1,zan=0;
memset(lia,0,sizeof(lia));
}
}
cout<<sum;
return 0;
}
每找到两个成对的或者四个一样的算一句。找到后前面的都归零 -
02017-10-19 22:25:21@
#include <cstdio>
int main() {
int n, a[10005], r = 0, c = 0, f = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
#ifdef LOCAL
puts("===");
#endif
for(int i = 0; i < n; i++) {
for(int j = f; j < i; j++) {
if(a[i] == a[j]) {
c++;
#ifdef LOCAL
printf("a[%d] == a[%d]: %d\n", i, j, a[i]);
for(int o = 0; o < n; o++)
printf("%d ", a[o]);
printf("\n");
#endif
a[i] = a[j] = 0;
break;
}
}
if(c == 2)
r++, c = 0, f = i;
}
printf("%d", r);
return 0;
} -
02017-10-19 22:24:57@
#include <cstdio>
int main() {
int n, a[10005], r = 0, c = 0, f = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
#ifdef LOCAL
puts("===");
#endif
for(int i = 0; i < n; i++) {
for(int j = f; j < i; j++) {
if(a[i] == a[j]) {
c++;
#ifdef LOCAL
printf("a[%d] == a[%d]: %d\n", i, j, a[i]);
for(int o = 0; o < n; o++)
printf("%d ", a[o]);
printf("\n");
#endif
a[i] = a[j] = 0;
break;
}
}
if(c == 2)
r++, c = 0, f = i;
}
printf("%d", r);
return 0;
} -
02015-02-08 16:39:21@
对于我这样的水人,这样的题永远都不水。
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int a[4007];
int len[4007];//from i how long it takes to form a string
int second[4007];
int size;
int ans;
void xxyy(){
int i,j;
for (i = 0; i < size; i++){
for (j = second[i] + 1; j < len[i]; j++){
if (len[i]>second[j]){
len[i] = second[j];
}
}
}
}
void xyxyORxyyx(){
int i, j;
for (i = 0; i < size; i++){
for (j = i + 1; j < len[i]; j++){
if (a[i] == a[j])continue;
if (second[j] < second[i]){
if (len[i]>second[i])len[i] = second[i];
}
else if(second[j]>second[i]){
if (len[i]>second[j])len[i] = second[j];
}
}
}
}
void go(){
int i=0;
ans = 0;
while (1){
int mi = i;
for (; i < len[mi]; i++){
if (len[i] < len[mi])mi = i;
}
i = len[mi]+1;
if (i<=size)ans++;
if(i>=size)break;
}
}
int main(){
freopen("in.txt", "r", stdin);
cin >> size;
int i;
for (i = 0; i < size; i++)cin >> a[i];
memset(len, 0, sizeof(len));
for (i = 0; i < size; i++)len[i] = size;
int last[10001];
memset(last, -1, sizeof(last));
for (i = 0; i < size; i++)second[i] = size;
for (i = 0; i < size; i++){
if (last[a[i]] != -1){
second[last[a[i]]] = i;
}
last[a[i]] = i;
}
xxyy();
xyxyORxyyx();
go();
cout << ans << endl;
return 0;
} -
02014-08-05 17:28:35@
贪心。。。
不能再水。
program p1236;
var n:longint;
a:array[0..4010] of longint;
h:array[0..10010] of longint;
i,sum,sum1,p1:longint;
//
procedure make;
var j:longint;
begin
for j:=p1+1 to i do dec(h[a[j]]);p1:=i;
end;
//
begin
read(n);
for i:=1 to n do
begin
read(a[i]);inc(h[a[i]]);
if h[a[i]]=2 then inc(sum1);
if sum1=2 then
begin
make;inc(sum);sum1:=0;
end;
if h[a[i]]=4 then
begin
make;inc(sum);sum1:=0;
end;
end;
write(sum);
end. -
02009-10-17 12:35:46@
Accepted 有效得分:100 有效耗时:0ms
贪心是正解,不一定要DP。
但是各位注意楼下的有误导!只有下面两种是可行的:
1.f[x]=4
2.f[x]=2并且前面出现过一个数字f[i]=2!(这点可以用flag真值来表示) -
02009-10-15 19:41:39@
“按顺序选”,因此可以用贪心优化。
还是多费点时间写正确的算法呀。 -
02009-09-24 15:18:31@
hash:pre[i]记录第i个数字在前面出现的位置,剩下来的就很简单了。
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02009-08-31 11:09:48@
第190题纪念。。。淅沥糊涂就过了
My Answer:
[red]
var n,i,j,total:longint;
a:array[1..10000] of longint;
h:boolean;begin
readln(n);
total:=0;
fillchar(a,sizeof(a),0);
h:=false;
for i:= 1 to n do
begin
read(j);
inc(a[j]);
if a[j] = 2 then
begin
if h then
begin
h:=false;
inc(total);
fillchar(a,sizeof(a),0);
end
else
h:=true;
end;
end;
writeln(total);
end.
[/red] -
02009-08-04 19:51:51@
职业生涯第200题,上帝的爱好
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02009-08-03 14:46:07@
我觉得贪心是正解~看你怎么贪了
---|---|---|---|---|---|---|---|---|
对于楼下的楼下,贪心结果是3
结果是1的话,就是你贪心方法错了~
---|---|---|---|---|---|---|---|---|
贪心也是有方法,要讲技巧地~~~PS:本人的第180题,庆祝~~~
-
02009-07-22 21:16:38@
都怎么了,正解绝对是动态规划,预处理是n^2,动规是n^2,贪心能过是数据太弱了啊!
-
02009-07-02 20:02:09@
贪心应该不正确吧?
对于这个数据:
16
1 2 3 3 4 4 5 5 6 6 7 7 8 8 2 1
贪心结果是1,但最优解为3....
请教大牛. -
02009-06-14 16:45:27@
简单!搜一遍就ok。秒杀!
---|---|---|---|---|---|---|---|---|---|
关键点:
1和2有多少中排列方式呢?
6种!
刚好把题目要求的xxyy,yxyx,yxxy,当然再补充个xxxx就搞定
然后就是线性的时间复杂度。完毕!
---|---|---|---|---|--
不知道出题的人是怎么想的.....好水.....
---|---|---|---|---|---|---|---|--
纯数学方法,排列组合 -
02009-05-23 16:06:46@
神啊,俺语文不好,能不能把题目说清楚点啊!
-
02009-05-09 03:11:07@
#include "stdio.h"
int main()
{
int n,i,j,x,find,ans,a[4010]={0};
scanf("%d",&n);
find=0;ans=0;
for(i=1;i