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();}

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

AI Hentai Generator
AIヘンタイを無料で生成します。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











公式アカウントのWebページはキャッシュを更新します。これはシンプルでシンプルで、ポットを飲むのに十分な複雑です。あなたは公式のアカウントの記事を更新するために一生懸命働きましたが、ユーザーはまだ古いバージョンを開くことができますか?この記事では、この背後にあるtwist余曲折と、この問題を優雅に解決する方法を見てみましょう。それを読んだ後、さまざまなキャッシュの問題に簡単に対処でき、ユーザーが常に新鮮なコンテンツを体験できるようになります。最初に基本について話しましょう。それを率直に言うと、アクセス速度を向上させるために、ブラウザまたはサーバーはいくつかの静的リソース(写真、CSS、JSなど)やページコンテンツを保存します。次回アクセスするときは、もう一度ダウンロードすることなく、キャッシュから直接検索できます。自然に高速です。しかし、このことは両刃の剣でもあります。新しいバージョンはオンラインです、

この記事では、ブラウザのユーザー入力を直接検証するために、必要、パターン、MIN、MAX、および長さの制限などのHTML5フォーム検証属性を使用して説明します。

記事では、HTML5クロスブラウザーの互換性を確保するためのベストプラクティスについて説明し、機能検出、プログレッシブエンハンスメント、およびテスト方法に焦点を当てています。

この記事では、CSSを使用したWebページへの効率的なPNG境界追加を示しています。 CSSはJavaScriptやライブラリと比較して優れたパフォーマンスを提供し、微妙または顕著な効果のために境界幅、スタイル、色を調整する方法を詳述していると主張しています

この記事では、HTML&lt; Datalist&GT;について説明します。オートコンプリートの提案を提供し、ユーザーエクスペリエンスの改善、エラーの削減によりフォームを強化する要素。

この記事では、HTML&lt; Progress&gt;について説明します。要素、その目的、スタイリング、および&lt; meter&gt;との違い要素。主な焦点は、&lt; Progress&gt;を使用することです。タスクの完了と&lt; Meter&gt; statiの場合

この記事では、html5&lt; time&gt;について説明します。セマンティックデート/時刻表現の要素。 人間の読み取り可能なテキストとともに、マシンの読みやすさ(ISO 8601形式)のDateTime属性の重要性を強調し、Accessibilitを増やします

この記事では、html&lt; meter&gt;について説明します。要素は、範囲内でスカラーまたは分数値を表示するために使用され、Web開発におけるその一般的なアプリケーション。それは差別化&lt; Meter&gt; &lt; Progress&gt;およびex
