cf 556C Case of Matryoshkas
http://codeforces.com/contest/556/problem/C
果然一晚上不睡觉会导致读错题么...
需要注意的是 如果有一个是 1 2 4 6 那么 1,2是不必拆开的....
然后我们发现,只有以1为开始且连续的套娃不必拆开....
可以先假设所有都需要拆开,那么一共需要 2*n-k-1次
然后如果有以1为开始连续的,拆的时候少拆一次,装的时候少装一次,所以ans=ans-2
但是需要注意的是....如果只有一个1,比如1 3 5 也算成了长度为1的以1开始连续的,但是这并没有什么卵用....所以最后答案记得ans+2
1
2/*************************************************************************
3 > File Name: code/cf/556C.cpp
4 > Author: 111qqz
5 > Email: rkz2013@126.com
6 > Created Time: 2015年07月12日 星期日 10时24分54秒
7 ************************************************************************/
8
9#include<iostream>
10#include<iomanip>
11#include<cstdio>
12#include<algorithm>
13#include<cmath>
14#include<cstring>
15#include<string>
16#include<map>
17#include<set>
18#include<queue>
19#include<vector>
20#include<stack>
21using namespace std;
22typedef long long LL;
23typedef unsigned long long ULL;
24const int N=1E5+7;
25int a[N],m[N];
26LL n,k,ans;
27int main()
28{
29 cin>>n>>k;
30 ans = 2*n-k+1;
31 for (int i = 0 ; i < k ; i++ )
32 {
33 scanf("%d",&m[i]);
34 for (int j = 0 ; j < m[i];j++)
35 {
36 scanf("%d",&a[j]);
37 if (a[j]==j+1)
38 ans = ans -2;
39
40 }
41 }
42 cout<<ans<<endl;
43 return 0;
44}
45