1559.md (6050B)
1 Source: https://codeforces.com/blog/entry/93898 2 3 Tutorial is loading... 4 5 **solution** 6 7 ``` 8 #include<bits/stdc++.h> 9 #define inf 0x3f3f3f3f 10 #define maxm 100005 11 #define maxn 2005 12 #define PII pair<int, int> 13 #define fi first 14 #define se second 15 typedef long long ll; 16 typedef unsigned long long ull; 17 using namespace std; 18 const double pi = acos(-1); 19 const int mod = 998244353; 20 const double eps = 1e-10; 21 const int N =1e2+10; 22 int n; 23 int a[N]; 24 int main() { 25 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 26 //int a,b,c; 27 int t; 28 cin>>t; 29 while(t--){ 30 cin>>n; 31 for(int i=1;i<=n;i++)cin>>a[i]; 32 int res=a[1]; 33 for(int i=2;i<=n;i++)res&=a[i]; 34 cout<<res<<endl; 35 } 36 return 0; 37 } 38 ``` 39 40 Tutorial is loading... 41 42 **solution** 43 44 ``` 45 #include <cstdio> 46 using namespace std; 47 const int N=105; 48 int t,n,cnt; 49 char s[N]; 50 int main() 51 { 52 scanf("%d",&t); 53 while (t--) 54 { 55 cnt=0; 56 scanf("%d",&n); 57 scanf("%s",s+1); 58 for (int i=1;i<=n;i++) 59 cnt+=(s[i]!='?'); 60 if (!cnt) 61 s[1]='R'; 62 for (int i=2;i<=n;i++) 63 if (s[i]=='?'&&s[i-1]!='?') 64 s[i]=s[i-1]^('B'^'R'); 65 for (int i=n-1;i;i--) 66 if (s[i]=='?'&&s[i+1]!='?') 67 s[i]=s[i+1]^('B'^'R'); 68 printf("%s\n",s+1); 69 } 70 return 0; 71 } 72 ``` 73 74 Tutorial is loading... 75 76 **solution** 77 78 ``` 79 #include <bits/stdc++.h> 80 #define maxn 100086 81 82 using namespace std; 83 84 int t, n; 85 int a[maxn]; 86 87 void solve(){ 88 scanf("%d", &n); 89 for(int i = 1;i <= n;i++) scanf("%d", &a[i]); 90 if(a[1]){ 91 printf("%d ", n + 1); 92 for(int i = 1;i <= n;i++) printf("%d ", i); 93 return; 94 } 95 for(int i = 1;i < n;i++){ 96 if(!a[i] && a[i + 1]){ 97 for(int j = 1;j <= i;j++) printf("%d ", j); 98 printf("%d ", n + 1); 99 for(int j = i + 1;j <= n;j++) printf("%d ", j); 100 return; 101 } 102 } 103 for(int i = 1;i <= n;i++) printf("%d ", i); 104 printf("%d ", n + 1); 105 } 106 107 int main(){ 108 scanf("%d", &t); 109 while(t--) solve(), puts(""); 110 } 111 ``` 112 113 Tutorial is loading... 114 115 **solution** 116 117 ``` 118 #include<bits/stdc++.h> 119 #define maxn 2005 120 #define fi first 121 #define se second 122 #define PII pair<int, int> 123 124 using namespace std; 125 126 typedef long long ll; 127 const ll mod = 10007; 128 129 inline ll read(){ 130 ll x = 0, f = 1;char ch = getchar(); 131 while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();} 132 while(ch >= '0' && ch <= '9'){x = x * 10 + ch -'0';ch = getchar();} 133 return x * f; 134 } 135 136 int n, m1, m2, f[2][maxn]; 137 138 int getf(int id, int x){return x == f[id][x] ? x : f[id][x] = getf(id, f[id][x]);} 139 140 vector<PII> ans; 141 142 int main() { 143 n = read(), m1 = read(), m2 = read(); 144 145 for(int i = 1; i <= n; i++) 146 f[0][i] = f[1][i] = i; 147 148 for(int i = 1; i <= m1; i++){ 149 int u = read(), v = read(); 150 int fu = getf(0, u), fv = getf(0, v); 151 f[0][fu] = fv; 152 } 153 154 for(int i = 1; i <= m2; i++){ 155 int u = read(), v = read(); 156 int fu = getf(1, u), fv = getf(1, v); 157 f[1][fu] = fv; 158 } 159 160 for(int i = 1; i <= n; i++){ 161 for(int j = i + 1; j <= n; j++){ 162 if(getf(0, i) != getf(0, j) && getf(1, i) != getf(1, j)){ 163 ans.push_back({i, j}); 164 f[0][getf(0, i)] = getf(0, j); 165 f[1][getf(1, i)] = getf(1, j); 166 } 167 } 168 } 169 170 printf("%d\n", ans.size()); 171 for(auto i: ans) printf("%d %d\n", i.fi, i.se); 172 return 0; 173 } 174 ``` 175 176 Tutorial is loading... 177 178 **solution** 179 180 ``` 181 #include<bits/stdc++.h> 182 using namespace std; 183 #define N 100010 184 int fa1[N],fa2[N]; 185 set<pair<int,int> > rows; 186 set<int> row[N],col[N]; 187 set<int>::iterator it; 188 map<int,int> mp[N]; 189 pair<int,int> Ans[N]; 190 int getfa(int *fa,int x){ 191 if (x==fa[x]){ 192 return x; 193 } 194 return fa[x]=getfa(fa,fa[x]); 195 } 196 void Merge_row(int x,int y){ 197 for (it=row[y].begin();it!=row[y].end();it++){ 198 mp[x][*it]=mp[y][*it]; 199 row[x].insert(*it); 200 col[*it].erase(y); 201 col[*it].insert(x); 202 } 203 } 204 void Merge_col(int x,int y){ 205 for (it=col[y].begin();it!=col[y].end();it++){ 206 mp[*it][x]=mp[*it][y]; 207 col[x].insert(*it); 208 row[*it].erase(y); 209 row[*it].insert(x); 210 } 211 } 212 int main(){ 213 int n,m1,m2,h=0,i; 214 scanf("%d%d%d",&n,&m1,&m2); 215 for (i=1;i<=n;i++){ 216 fa1[i]=fa2[i]=i; 217 } 218 for (i=1;i<=m1;i++){ 219 int x,y; 220 scanf("%d%d",&x,&y); 221 int p=getfa(fa1,x),q=getfa(fa1,y); 222 fa1[p]=q; 223 } 224 for (i=1;i<=m2;i++){ 225 int x,y; 226 scanf("%d%d",&x,&y); 227 int p=getfa(fa2,x),q=getfa(fa2,y); 228 fa2[p]=q; 229 } 230 if (m1<m2){ 231 swap(fa1,fa2); 232 } 233 234 for (i=1;i<=n;i++){ 235 int p1=getfa(fa1,i),p2=getfa(fa2,i); 236 mp[p1][p2]=i; 237 row[p1].insert(p2); 238 col[p2].insert(p1); 239 } 240 for (i=1;i<=n;i++){ 241 if (getfa(fa1,i)==i){ 242 rows.insert(make_pair(-row[i].size(),i)); 243 } 244 } 245 246 while (rows.size()>1){ 247 int x=rows.begin()->second; 248 rows.erase(rows.begin()); 249 int y=rows.begin()->second; 250 rows.erase(rows.begin()); 251 if (row[x].size()<row[y].size()){ 252 swap(x,y); 253 } 254 it=row[x].begin(); 255 int a=*it,b=*row[y].begin(); 256 if (a==b){ 257 a=*++it; 258 } 259 Ans[++h]=make_pair(mp[x][a],mp[y][b]); 260 if (col[a].size()<col[b].size()){ 261 swap(a,b); 262 } 263 Merge_row(x,y); 264 Merge_col(a,b); 265 rows.insert(make_pair(-row[x].size(),x)); 266 } 267 268 printf("%d\n",h); 269 for (i=1;i<=h;i++){ 270 printf("%d %d\n",Ans[i].first,Ans[i].second); 271 } 272 return 0; 273 } 274 ``` 275 276 Tutorial is loading... 277 278 **solution** 279 280 ``` 281 #include <bits/stdc++.h> 282 #define maxn 100086 283 284 using namespace std; 285 286 const int p = 998244353; 287 288 int n, m; 289 int l[maxn], r[maxn]; 290 int f[maxn], sum[maxn]; 291 292 int cal(int d){ 293 int M = m / d; 294 f[0] = 1; 295 for(int i = 1;i <= M;i++) f[i] = 0; 296 for(int i = 1;i <= n;i++){ 297 int L = (l[i] + d - 1) / d, R = r[i] / d; 298 if(L > R) return 0; 299 for(int j = 0;j <= M;j++) sum[j] = (f[j] + (j ? sum[j - 1] : 0)) % p; 300 for(int j = 0;j <= M;j++){ 301 f[j] = ((j - L >= 0 ? sum[j - L] : 0) + p - (j - R - 1 >= 0 ? sum[j - R - 1] : 0)) % p; 302 } 303 } 304 int ans = 0; 305 for(int i = 1;i <= M;i++) ans = (ans + f[i]) % p; 306 return ans; 307 } 308 309 int prm[maxn], cnt, mu[maxn]; 310 bool tag[maxn]; 311 312 int main(){ 313 scanf("%d%d", &n, &m); 314 for(int i = 1;i <= n;i++) scanf("%d%d", &l[i], &r[i]); 315 mu[1] = 1; 316 for(int i = 2;i <= m;i++){ 317 if(!tag[i]) prm[++cnt] = i, mu[i] = p - 1; 318 for(int j = 1;j <= cnt && prm[j] * i <= m;j++){ 319 tag[i * prm[j]] = true; 320 if(i % prm[j]) mu[i * prm[j]] = (p - mu[i]) % p; 321 else break; 322 } 323 } 324 int ans = 0; 325 for(int i = 1;i <= m;i++) ans = (ans + 1ll * mu[i] * cal(i)) % p; 326 printf("%d", ans); 327 } 328 ```