ホームページ >ウェブフロントエンド >htmlチュートリアル >codeforces Round #275(div2) D問題解決レポート_html/css_WEB-ITnose
D. 興味深い配列
テストごとの制限時間
1 秒
テストごとのメモリ制限
256 メガバイト
入力
標準入力
出力
標準出力
m個の制約を満たす場合、n個の非負の整数a[1]、?a[2]、?...、?a[n]の配列を興味深いと呼びます。 m 個の制約の i 番目は、3 つの整数 li、ri、qi (1?≤?li?≤?ri?≤?n) で構成されます。これは、値が qi に等しい必要があることを意味します。
あなたのタスクは、興味深いものを見つけることです。 n 要素の配列、またはそのような配列が存在しないことを示します。
式 x&y は、数値 x と y のビット単位の AND を意味します。プログラミング言語 C++、Java、Python では、この操作は Pascal では "&" として表されます。
入力
最初の行には 2 つの整数 n, m (1?≤?n?≤?105, 1?≤?m?≤?105)? が含まれています。配列内の要素の数と制限の数です。
次の m 行には、それぞれ 3 つの整数 li、ri、qi (1?≤?li?≤?ri?≤?n, 0?≤?qi?) が含まれています。 230) i 番目の制限を記述します。
出力
興味深い配列が存在する場合、最初の行に "YES" (引用符なし) を出力し、2 行目に n 整数 a[1] を出力します。 、?a[2]、?...、?a[n] (0?≤?a[i]?230) は、興味深い配列を記述します。複数の回答がある場合は、いずれかを出力します。
興味深い配列が存在しない場合は、単一行に「NO」(引用符なし) を出力します。
サンプル テスト
入力
3 11 3 3
出力
YES3 3 3
入力
3 21 3 31 3 2
出力
NO
假设有n个非负数,现在有m制限,a[l] & a[l+1] & a[l+2] ... & a[r] = q。 要求 前述の制限に従って、「いいえ」を出力できない場合は、要求に対応する 1 ~ n の数が出力されます。
解法:
私は先んじて探求し、明確な目给の既知条件と要我们出力物。
a[l] & a[l+1] & a[l+2] 。 .. & a[r] = q、これはそれぞれの制限の基本的な形式です、「&」によって知ることができます、例えば若qの中の特定のビットが 1 であるということ、a[l]~a[r] が必要ですこの条件は制限されているようで、変換により既知の条件、つまり各 a[i] のビットが必ず 1 になる可能性があります。 ,私たちは各 a[i] の基本値を取得しました、その後、各制限は 1 つの区域です、簡単に線区に到達できます、各条の制限を実行します、突発かどうかを確認します、突発が "NO" の場合、そうでない場合
代コード:
#include#include #define Maxbit 29#define M_max 123456#define N_max 123456#define root 1, 1, nusing namespace std;const int noth = (1<<30)-1;int n, m;int l[M_max], r[M_max], q[M_max], a[N_max];int sum[N_max], tree[N_max*3];void build(int v, int l, int r) { if (l == r) { tree[v] = a[l]; return; } int ls = v<<1, rs = ls+1, mid = (l+r)>>1; build(ls, l, mid); build(rs, mid+1, r); tree[v] = tree[ls] & tree[rs];}int query(int v, int l, int r, int ql, int qr) { if (r < ql || l > qr) return noth; if (ql <= l && r <= qr) return tree[v]; int ls = v<<1, rs = ls+1, mid = (l+r)>>1; return query(ls, l, mid, ql, qr) & query(rs, mid+1, r, ql, qr);}void init() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d%d", &l[i], &r[i], &q[i]); for (int i = 0; i <= Maxbit; i++) { memset(sum, 0, sizeof(sum)); for (int j = 1; j <= m; j++) if ((q[j] >> i) & 1) { sum[l[j]]++; sum[r[j]+1]--; } for (int j = 1; j <= n; j++) { sum[j] += sum[j-1]; if (sum[j] > 0) a[j] |= 1 << i; } } build(root);}void solve() { for (int i = 1; i <= m; i++) if (query(root, l[i], r[i]) != q[i]) { printf("NO\n"); return; } printf("YES\n"); for (int i = 1; i <= n; i++) printf("%d ", a[i]); printf("\n");}int main() { init(); solve();}