首页 > 代码库 > noj 2068 爱魔法的露露 [线性扫一遍]

noj 2068 爱魔法的露露 [线性扫一遍]

2024-08-01 20:43:26   217人阅读

njczy2010
2068
Accepted
325MS
  8052K
1450Byte
G++
2014-11-13 11:20:40.0

 

爱魔法的露露

时间限制(普通/Java) : 1200 MS/ 4000 MS          运行内存限制 : 65536 KByte
总提交 : 47            测试通过 : 3 

描述

    仙灵女巫露露，对于魔法的热忱可是超出常人，要是发现了什么上古遗留下的魔法，她总是想方设法地获得，然后研究分析。而最近，他又从邪恶小法师维嘉那里获得了一个“奇怪”的魔法卷轴；

    这个魔法卷轴上有一大串数字，而且根据卷轴上的描述，这个魔法的威力指数来自于这一串数字中“魔法区间”的数量；

    所谓“魔法区间”指的是一段连续的闭区间，且这段区间上的所有数字均不相同；

    现在，露露想知道这个魔法的威力指数，你能帮帮她么？


输入

 

先输入一个正整数T，表示样例个数，1≤T≤10。

对于每一个样例，先输入一个正整数n，表示卷轴上的数字个数(1≤n≤106)；

再输入n个整数，第i个数ai，表示卷轴上第i个数（0≤ai≤106）。

 

输出

 

对于每个样例，输出一个正整数，即威力指数。

题目保证结果在int范围内。

 

样例输入

1
3
1 2 3

样例输出

6

提示

 

  1. 读入数据请使用 scanf()；

  2. 对于样例，共有{1},{2},{3},{1,2},{2,3},{1,2,3}，6个魔法区间，所以威力为6。

 

题目来源

yuman

 
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<iostream> 7 #include<set> 8 #define maxi(a,b) (a)>(b)?(a):(b) 9 #define mini(a,b) (a)<(b)?(a):(b)10 #define N 100000511 #define mod 1000012 #define ll long long13 14 using namespace std;15 16 int T;17 int tot;18 set<int> s;19 int a[N];20 int n;21 int vis[N];22 23 void ini()24 {25     int i;26     tot=0;27     //s.clear();28     scanf("%d",&n);29     for(i=1;i<=n;i++){30         scanf("%d",&a[i]);31     }32     memset(vis,0,sizeof(vis));33 }34 35 void solve()36 {37     int i,j;38     i=1;j=1;39     for(j=1;j<=n;j++){40        // if(s.find(a[j])==s.end()){41         if(vis[ a[j] ]==0){42             vis[ a[j] ]++;43         }44         else{45             //j--;46             break;47         }48     }49    // tot+=j-i+1;50     while(i<=n)51     {52         //s.erase(a[i]);53         vis[ a[i] ]--;54         tot+=j-i;55         //printf(" i=%d j=%d tot=%d\n",i,j,tot);56         i++;57         for(;j<=n;j++){58            // if(s.find(a[j])==s.end()){59             if(vis[ a[j] ]==0){60                 vis[ a[j] ]++;61             }62             else{63                 //j--;64                 break;65             }66         }67     }68 }69 70 void out()71 {72     printf("%d\n",tot);73 }74 75 int main()76 {77    // freopen("data.in","r",stdin);78     scanf("%d",&T);79     while(T--)80    // while(scanf("%I64d",&n)!=EOF)81     {82         ini();83         solve();84         out();85     }86     return 0;87 }

 

noj 2068 爱魔法的露露 [线性扫一遍]


联系
我们