Tutorial is loading...
solution
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxm 100005
#define maxn 2005
#define PII pair<int, int>
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const double pi = acos(-1);
const int mod = 998244353;
const double eps = 1e-10;
const int N =1e2+10;
int n;
int a[N];
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//int a,b,c;
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int res=a[1];
for(int i=2;i<=n;i++)res&=a[i];
cout<<res<<endl;
}
return 0;
}
Tutorial is loading...
solution
#include <cstdio>
using namespace std;
const int N=105;
int t,n,cnt;
char s[N];
int main()
{
scanf("%d",&t);
while (t--)
{
cnt=0;
scanf("%d",&n);
scanf("%s",s+1);
for (int i=1;i<=n;i++)
cnt+=(s[i]!='?');
if (!cnt)
s[1]='R';
for (int i=2;i<=n;i++)
if (s[i]=='?'&&s[i-1]!='?')
s[i]=s[i-1]^('B'^'R');
for (int i=n-1;i;i--)
if (s[i]=='?'&&s[i+1]!='?')
s[i]=s[i+1]^('B'^'R');
printf("%s\n",s+1);
}
return 0;
}
Tutorial is loading...
solution
#include <bits/stdc++.h>
#define maxn 100086
using namespace std;
int t, n;
int a[maxn];
void solve(){
scanf("%d", &n);
for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
if(a[1]){
printf("%d ", n + 1);
for(int i = 1;i <= n;i++) printf("%d ", i);
return;
}
for(int i = 1;i < n;i++){
if(!a[i] && a[i + 1]){
for(int j = 1;j <= i;j++) printf("%d ", j);
printf("%d ", n + 1);
for(int j = i + 1;j <= n;j++) printf("%d ", j);
return;
}
}
for(int i = 1;i <= n;i++) printf("%d ", i);
printf("%d ", n + 1);
}
int main(){
scanf("%d", &t);
while(t--) solve(), puts("");
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
#define maxn 2005
#define fi first
#define se second
#define PII pair<int, int>
using namespace std;
typedef long long ll;
const ll mod = 10007;
inline ll read(){
ll x = 0, f = 1;char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch -'0';ch = getchar();}
return x * f;
}
int n, m1, m2, f[2][maxn];
int getf(int id, int x){return x == f[id][x] ? x : f[id][x] = getf(id, f[id][x]);}
vector<PII> ans;
int main() {
n = read(), m1 = read(), m2 = read();
for(int i = 1; i <= n; i++)
f[0][i] = f[1][i] = i;
for(int i = 1; i <= m1; i++){
int u = read(), v = read();
int fu = getf(0, u), fv = getf(0, v);
f[0][fu] = fv;
}
for(int i = 1; i <= m2; i++){
int u = read(), v = read();
int fu = getf(1, u), fv = getf(1, v);
f[1][fu] = fv;
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(getf(0, i) != getf(0, j) && getf(1, i) != getf(1, j)){
ans.push_back({i, j});
f[0][getf(0, i)] = getf(0, j);
f[1][getf(1, i)] = getf(1, j);
}
}
}
printf("%d\n", ans.size());
for(auto i: ans) printf("%d %d\n", i.fi, i.se);
return 0;
}
Tutorial is loading...
solution
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int fa1[N],fa2[N];
set<pair<int,int> > rows;
set<int> row[N],col[N];
set<int>::iterator it;
map<int,int> mp[N];
pair<int,int> Ans[N];
int getfa(int *fa,int x){
if (x==fa[x]){
return x;
}
return fa[x]=getfa(fa,fa[x]);
}
void Merge_row(int x,int y){
for (it=row[y].begin();it!=row[y].end();it++){
mp[x][*it]=mp[y][*it];
row[x].insert(*it);
col[*it].erase(y);
col[*it].insert(x);
}
}
void Merge_col(int x,int y){
for (it=col[y].begin();it!=col[y].end();it++){
mp[*it][x]=mp[*it][y];
col[x].insert(*it);
row[*it].erase(y);
row[*it].insert(x);
}
}
int main(){
int n,m1,m2,h=0,i;
scanf("%d%d%d",&n,&m1,&m2);
for (i=1;i<=n;i++){
fa1[i]=fa2[i]=i;
}
for (i=1;i<=m1;i++){
int x,y;
scanf("%d%d",&x,&y);
int p=getfa(fa1,x),q=getfa(fa1,y);
fa1[p]=q;
}
for (i=1;i<=m2;i++){
int x,y;
scanf("%d%d",&x,&y);
int p=getfa(fa2,x),q=getfa(fa2,y);
fa2[p]=q;
}
if (m1<m2){
swap(fa1,fa2);
}
for (i=1;i<=n;i++){
int p1=getfa(fa1,i),p2=getfa(fa2,i);
mp[p1][p2]=i;
row[p1].insert(p2);
col[p2].insert(p1);
}
for (i=1;i<=n;i++){
if (getfa(fa1,i)==i){
rows.insert(make_pair(-row[i].size(),i));
}
}
while (rows.size()>1){
int x=rows.begin()->second;
rows.erase(rows.begin());
int y=rows.begin()->second;
rows.erase(rows.begin());
if (row[x].size()<row[y].size()){
swap(x,y);
}
it=row[x].begin();
int a=*it,b=*row[y].begin();
if (a==b){
a=*++it;
}
Ans[++h]=make_pair(mp[x][a],mp[y][b]);
if (col[a].size()<col[b].size()){
swap(a,b);
}
Merge_row(x,y);
Merge_col(a,b);
rows.insert(make_pair(-row[x].size(),x));
}
printf("%d\n",h);
for (i=1;i<=h;i++){
printf("%d %d\n",Ans[i].first,Ans[i].second);
}
return 0;
}
Tutorial is loading...
solution
#include <bits/stdc++.h>
#define maxn 100086
using namespace std;
const int p = 998244353;
int n, m;
int l[maxn], r[maxn];
int f[maxn], sum[maxn];
int cal(int d){
int M = m / d;
f[0] = 1;
for(int i = 1;i <= M;i++) f[i] = 0;
for(int i = 1;i <= n;i++){
int L = (l[i] + d - 1) / d, R = r[i] / d;
if(L > R) return 0;
for(int j = 0;j <= M;j++) sum[j] = (f[j] + (j ? sum[j - 1] : 0)) % p;
for(int j = 0;j <= M;j++){
f[j] = ((j - L >= 0 ? sum[j - L] : 0) + p - (j - R - 1 >= 0 ? sum[j - R - 1] : 0)) % p;
}
}
int ans = 0;
for(int i = 1;i <= M;i++) ans = (ans + f[i]) % p;
return ans;
}
int prm[maxn], cnt, mu[maxn];
bool tag[maxn];
int main(){
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++) scanf("%d%d", &l[i], &r[i]);
mu[1] = 1;
for(int i = 2;i <= m;i++){
if(!tag[i]) prm[++cnt] = i, mu[i] = p - 1;
for(int j = 1;j <= cnt && prm[j] * i <= m;j++){
tag[i * prm[j]] = true;
if(i % prm[j]) mu[i * prm[j]] = (p - mu[i]) % p;
else break;
}
}
int ans = 0;
for(int i = 1;i <= m;i++) ans = (ans + 1ll * mu[i] * cal(i)) % p;
printf("%d", ans);
}