codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```