- 1 //WA1
- 2#include 3 using namespace std;
- 4 int n,
- m;
- 5 int s[50010];
- 6 int mp[50010],
- v[50010];
- 7 vectorint > >t;
- 8 bool cmp(const vector < int > &a, const vector < int > &b) 9 {
- 10
- return a.size() < b.size();
- 11
- }
- 12 maplong long,
- int > table;
- 13 const unsigned long long HASHNUM = 1000000007,
- p = 1000009;
- 14 template < class T > 15 unsigned long long HASH(T & t) 16 {
- 17 unsigned long long ans = 0;
- 18
- for (auto it = t.begin(); it != t.end(); it++) ans = (ans + ( * it) * p) % HASHNUM;
- 19
- return ans;
- 20
- }
- 21 void cal(int l) 22 {
- 23 multiset < int > st;
- 24
- for (int i = 0; i) st.insert(s[i]);
- 25 table.clear();
- 26
- for (int i = l; i <= n; i++) 27 {
- 28 table[HASH(st)]++;
- 29 st.erase(st.find(s[i - l]));
- 30 st.insert(s[i]);
- 31
- }
- 32
- }
- 33 maplong long,
- int > id;
- 34 int ans[50010];
- 35 int main() 36 {
- 37
- while (scanf("%d", &n) == 1) 38 {
- 39
- for (int i = 0; i "%d", s + i);
- 40 scanf("%d", &m);
- 41
- for (int i = 0; i) 42 {
- 43 int k,
- x;
- 44 scanf("%d", &k);
- 45 vector < int > tmp;
- 46
- while (k--) scanf("%d", &x),
- tmp.push_back(x);
- 47 sort(tmp.begin(), tmp.end());
- 48 id[HASH(tmp)] = i;
- 49 t.push_back(tmp);
- 50
- }
- 51 sort(t.begin(), t.end(), cmp);
- 52
- for (int i = 0; i < m;) 53 {
- 54 int j = i;
- 55
- while (j; 56 cal(t[i].size()); 57
- for (int k = i; ktable[HASH(t[k])]; 58 i = j; 59
- }
- 60
- for (int i = 0; i "%dn", ans[i]); 61
- }
- 62
- return 0;
- 63
- }
- 64 //WA2
- 65#include 66 using namespace std;
- 67 int n,
- m;
- 68 int s[50010];
- 69 int mp[50010],
- v[50010];
- 70 vectorint > >t;
- 71 bool cmp(const vector < int > &a, const vector < int > &b) 72 {
- 73
- return a.size() < b.size();
- 74
- }
- 75 maplong long,
- int > table;
- 76 const unsigned long long HASHNUM = 1000007,
- p = 10009;
- 77 template < class T > 78 unsigned long long HASH(T & t) 79 {
- 80 unsigned long long ans = 0;
- 81
- for (auto it = t.begin(); it != t.end(); it++) ans = (ans + ( * it) * p) % HASHNUM;
- 82
- return ans;
- 83
- }
- 84 void cal(int l) 85 {
- 86 multiset < int > st;
- 87
- for (int i = 0; i) st.insert(s[i]);
- 88 table.clear();
- 89
- for (int i = l; i <= n; i++) 90 {
- 91 table[HASH(st)]++;
- 92 st.erase(st.find(s[i - l]));
- 93 st.insert(s[i]);
- 94
- }
- 95
- }
- 96 maplong long,
- int > id;
- 97 int ans[50010];
- 98 int main() 99 {
- 100
- while (scanf("%d", &n) == 1) 101 {
- 102
- for (int i = 0; i "%d", s + i);
- 103 scanf("%d", &m);
- 104
- for (int i = 0; i) 105 {
- 106 int k,
- x;
- 107 scanf("%d", &k);
- 108 vector < int > tmp;
- 109
- while (k--) scanf("%d", &x),
- tmp.push_back(x);
- 110 sort(tmp.begin(), tmp.end());
- 111 id[HASH(tmp)] = i;
- 112 t.push_back(tmp);
- 113
- }
- 114 sort(t.begin(), t.end(), cmp);
- 115
- for (int i = 0; i < m;) 116 {
- 117 int j = i;
- 118
- while (j; 119 cal(t[i].size()); 120
- for (int k = i; ktable[HASH(t[k])]; 121 i = j; 122
- }
- 123
- for (int i = 0; i "%dn", ans[i]); 124
- }
- 125
- return 0;
- 126
- }
- 127 //WA3
- 128#include 129 using namespace std;
- 130 int n,
- m;
- 131 int s[50010];
- 132 int mp[50010],
- v[50010];
- 133 maplong long,
- int > table;
- 134 unsigned long long randnum[50010];
- 135 const unsigned long long HASHNUM = 1000000007,
- p = 1000009;
- 136 template < class T > 137 unsigned long long HASH(T & t) 138 {
- 139 unsigned long long ans = 0;
- 140
- for (auto it = t.begin(); it != t.end(); it++) ans = (ans + randnum[ * it]) % HASHNUM;
- 141
- return ans;
- 142
- }
- 143 void cal(int l) 144 {
- 145 multiset < int > st;
- 146
- for (int i = 0; i) st.insert(s[i]);
- 147 table.clear();
- 148
- for (int i = l; i <= n; i++) 149 {
- 150 table[HASH(st)]++;
- 151 st.erase(st.find(s[i - l]));
- 152 st.insert(s[i]);
- 153
- }
- 154
- }
- 155 struct node 156 {
- 157 unsigned long long hash;
- 158 int len,
- i;
- 159 bool operator < (const node & a) 160 {
- 161
- return len < a.len;
- 162
- }
- 163
- };
- 164 int ans[50010];
- 165 vectort;
- 166 int main() 167 {
- 168
- for (int i = 0; i < 50010; i++) randnum[i] = 1ULL * (rand() * p) + rand();
- 169
- while (scanf("%d", &n) == 1) 170 {
- 171
- for (int i = 0; i "%d", s + i);
- 172 scanf("%d", &m);
- 173
- for (int i = 0; i) 174 {
- 175 int k,
- x;
- 176 scanf("%d", &k);
- 177 vector < int > tmp;
- 178
- while (k--) scanf("%d", &x),
- tmp.push_back(x);
- 179 node tmpn;
- 180 tmpn.hash = HASH(tmp);
- 181 tmpn.i = i;
- 182 tmpn.len = tmp.size();
- 183 t.push_back(tmpn);
- 184
- }
- 185 sort(t.begin(), t.end());
- 186
- for (int i = 0; i < m;) 187 {
- 188 int j = i;
- 189
- while (j; 190 cal(t[i].len); 191
- for (int k = i; ktable[t[k].hash]; 192 i = j; 193
- }
- 194
- for (int i = 0; i "%dn", ans[i]); 195
- }
- 196
- return 0;
- 197
- }
- 198 //WA4
- 199#include 200 using namespace std;
- 201 int n,
- m;
- 202 int s[50010];
- 203 int mp[50010],
- v[50010];
- 204 maplong long,
- int > table;
- 205 unsigned long long randnum[50010];
- 206 const unsigned long long HASHNUM = 1000000007,
- p = 1000009;
- 207 template < class T > 208 unsigned long long HASH(T & t) 209 {
- 210 unsigned long long ans = 0;
- 211
- for (auto it = t.begin(); it != t.end(); it++) ans = (ans + randnum[ * it]) % HASHNUM;
- 212
- return ans;
- 213
- }
- 214 void cal(int l) 215 {
- 216 multiset < int > st;
- 217
- for (int i = 0; i) st.insert(s[i]);
- 218 table.clear();
- 219
- for (int i = l; i <= n; i++) 220 {
- 221 table[HASH(st)]++;
- 222 st.erase(st.find(s[i - l]));
- 223 st.insert(s[i]);
- 224
- }
- 225
- }
- 226 struct node 227 {
- 228 unsigned long long hash;
- 229 int len,
- i;
- 230 bool operator < (const node & a) 231 {
- 232
- return len < a.len;
- 233
- }
- 234
- };
- 235 int ans[50010];
- 236 vectort;
- 237 int main() 238 {
- 239
- for (int i = 0; i < 50010; i++) randnum[i] = 1ULL * ((rand() * p) + rand() * p) + rand();
- 240
- while (scanf("%d", &n) == 1) 241 {
- 242
- for (int i = 0; i "%d", s + i);
- 243 scanf("%d", &m);
- 244
- for (int i = 0; i) 245 {
- 246 int k,
- x;
- 247 scanf("%d", &k);
- 248 vector < int > tmp;
- 249
- while (k--) scanf("%d", &x),
- tmp.push_back(x);
- 250 node tmpn;
- 251 tmpn.hash = HASH(tmp);
- 252 tmpn.i = i;
- 253 tmpn.len = tmp.size();
- 254 t.push_back(tmpn);
- 255
- }
- 256 sort(t.begin(), t.end());
- 257
- for (int i = 0; i < m;) 258 {
- 259 int j = i;
- 260
- while (j; 261 cal(t[i].len); 262
- for (int k = i; ktable[t[k].hash]; 263 i = j; 264
- }
- 265
- for (int i = 0; i "%dn", ans[i]); 266
- }
- 267
- return 0;
- 268
- }
来源: http://www.bubuko.com/infodetail-2102544.html