第 20 回 Codeforces コンテストが終了 #276 Div 2_html/css_WEB-ITnose

本当に色々な状況があったCFでした…

ついにアンレイテッドになりました 夜中にCFをやっていた私達はホッとしました(途中退場者も多かったです) )...パフォーマンスは良くありませんでしたが...

A-E および AC コードからの質問を含む、この codeforces セッションの問題解決レポートをここに書きます。 いくつかの質問には簡単な分析が含まれています。メインコードを理解するのが難しい。

問題についての質問

# 著者の問題 質問の回答 お知らせ ***** *****

A.工場

テストごとの時間制限

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

ある工業工場は作業計画を改革しています。監督は、神話的なディテールの制作基準を設定することを提案しました。一日の初めに工場の保管場所に x 個の詳細があった場合、その日の終わりまでに工場はさらに多くの詳細（x を m で割った余り）を生成する必要があります。残念ながら、神話的なディテールを購入した顧客は一人もいないため、生産されたすべてのディテールは工場に保管されたままです。

取締役会は、指定された計画による生産が最終的に停止するのではないかと心配しています (つまり、いつか生産が中止される可能性があります)。工場の現在の詳細の数は m で割り切れます)。

初日の詳細の数 a と数値 m を考慮して、ある時点で生産が停止するかどうかを確認します。

入力

最初の行には 2 つの整数が含まれていますa and m (1?≤?a,?m?≤?105).

出力

最終的に生産が停止する場合は「Yes」 (引用符なし) を出力し、それ以外の場合は「No」を出力します。

サンプルテスト

入力

1 5

出力

No

入力

3 6

出力

Yes

给两个数字a和m、工厂次回見て、a はどのように生れますか、その後、a は a%m になります、結果 a が 0 である場合、工順崩壊盘、问が崩壊するかどうかを確認します残りの数が使用されているかどうか、その後模倣する、毎回確認します現在の残りの数、場合は残りの数が0了出力はい、場合は残りの数がすでに存在する場合、残りの数の位置、那么就会これは一循環永続循環下去、那么我们休憩，输出No

コード：

#include <cmath> #include <cctype>#include <cstdio>#include <string>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)>a>>m;	int vis[100086]={0};	while(1)	{		if(a==0){cout </algorithm></iostream></cstring></cstdlib></string></cstdio></cctype></cmath>

B.貴重なリソース

テストごとの時間制限

1 秒

テストごとのメモリ制限 256 メガバイト

入力 標準入力

出力 標準出力

多くのコンピューター戦略ゲームでは、都市を建設し、軍隊を募集する必要があります、部族を征服し、資源を収集します。時にはそれが興味深い問題につながることもあります。

あなたの仕事が正方形の都市を建設することであると仮定しましょう。世界地図はデカルト座標を使用します。都市の側面は座標軸と平行である必要があります。マップには貴重な資源を含む鉱山が含まれており、整数の座標を持ついくつかの点に配置されています。地雷のサイズは比較的小さいため、ポイントとして扱うことができます。都市は、すべての鉱山が都市の広場の内側または境界上にあるように構築する必要があります。

都市の建設には、都市の規模に応じて多額の資金がかかるため、次の条件で都市を構築する必要があります。最低限の面積。鉱山の位置を考慮して、都市の最小面積を見つけます。

入力

The first line of the input contains number n ? the number of mines on the map (2?≤?n?≤?1000). Each of the next n lines contains a pair of integers xi and yi ? the coordinates of the corresponding mine (?-?109?≤?xi,?yi?≤?109). All points are pairwise distinct.

Output

Print the minimum area of the city that can cover all the mines with valuable resources.

Sample test(s)

input

20 02 2

output

input

20 00 3

output

有一个城市需要建造，给你许多矿坑d坐标点，问把这么多矿坑全都包进城市的话，城市所需最小面积是多少（注意，城市为平行于坐标轴的正方形）

这不知道算不算凸包，反正记录最大最小的x和y，然后相减获得最小矩形长宽，取两者较长边平方即可。

Code：

#include <cmath> #include <cctype>#include <cstdio>#include <string>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int inf=(int)1e9+10086;#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a) b;}int main(){	int n;	cin>>n;	int up=-inf,down=inf,left=inf,right=-inf;	for(int i=0;i<n int x cin>>x>>y;		if(x<left left="x;" if>right)	right=x;		if(y<down down="y;" if>up)	up=y;	}	int len=max(up-down,right-left);	cout  <br>  <p></p>  <p class="sycode">   </p>
<p class="sycode">    </p>
<p class="sycode">     </p>
<p class="sycode">      </p>
<p class="sycode">       </p>
<p class="sycode">        </p>
<h2 id="C-Bits">C. Bits</h2>        <p class="sycode">         </p>
<p class="sycode">          time limit per test         </p> 1 second                <p class="sycode">         </p>
<p class="sycode">          memory limit per test         </p> 256 megabytes                <p class="sycode">         </p>
<p class="sycode">          input         </p> standard input                <p class="sycode">         </p>
<p class="sycode">          output         </p> standard output                      <p class="sycode">        </p>
<p> Let's denote as  the number of bits set ('1' bits) in the binary representation of the non-negative integer x.</p>        <p> You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l?≤?x?≤?r, and is maximum possible. If there are multiple such numbers find the smallest of them.</p>              <p class="sycode">        </p>
<p class="sycode">         Input        </p>        <p> The first line contains integer n ? the number of queries (1?≤?n?≤?10000).</p>        <p> Each of the following n lines contain two integers li,?ri ? the arguments for the corresponding query (0?≤?li?≤?ri?≤?1018).</p>              <p class="sycode">        </p>
<p class="sycode">         Output        </p>        <p> For each query print the answer in a separate line.</p>              <p class="sycode">        </p>
<p class="sycode">         Sample test(s)        </p>        <p class="sycode">         </p>
<p class="sycode">          </p>
<p class="sycode">           input          </p>          <pre style="代码" class="precsshei">31 22 41 10

output

137

Note

The binary representations of numbers from 1 to 10 are listed below:

110?=?12

210?=?102

310?=?112

410?=?1002

510?=?1012

610?=?1102

710?=?1112

810?=?10002

910?=?10012

1010?=?10102

这题是给一个范围（L是左边界，R是有边界）问你在这个范围内哪个数载二进制下1的数量是最多的（有多个解请输出最小数）。

也就是，要二进制的1尽量多，还要求尽量小，那就从低位开始把0变成1呗

那么我们就从左边界开始，从低位向高位按位或（0变成1，1也还是1）1，直到比R大停止，输出前一个（即比R小的最后一个数）。

Code：

#include <cmath> #include <cctype>#include <cstdio>#include <string>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long ll;#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)>l>>r;		for(ll i=0;ir)break;			l=t,p  <br>  <p></p>  <p class="sycode">   </p>
<p class="sycode">    </p>
<p class="sycode">     </p>
<p class="sycode">      </p>
<p class="sycode">       </p>
<p class="sycode">        </p>
<h2 id="D-Maximum-Value">D. Maximum Value</h2>        <p class="sycode">         </p>
<p class="sycode">          time limit per test         </p> 1 second                <p class="sycode">         </p>
<p class="sycode">          memory limit per test         </p> 256 megabytes                <p class="sycode">         </p>
<p class="sycode">          input         </p> standard input                <p class="sycode">         </p>
<p class="sycode">          output         </p> standard output                      <p class="sycode">        </p>
<p> You are given a sequence a consisting of n integers. Find the maximum possible value of  (integer remainder of ai divided byaj), where 1?≤?i,?j?≤?n and ai?≥?aj.</p>              <p class="sycode">        </p>
<p class="sycode">         Input        </p>        <p> The first line contains integer n ? the length of the sequence (1?≤?n?≤?2·105).</p>        <p> The second line contains n space-separated integers ai (1?≤?ai?≤?106).</p>              <p class="sycode">        </p>
<p class="sycode">         Output        </p>        <p> Print the answer to the problem.</p>              <p class="sycode">        </p>
<p class="sycode">         Sample test(s)        </p>        <p class="sycode">         </p>
<p class="sycode">          </p>
<p class="sycode">           input          </p>          <pre style="代码" class="precsshei">33 4 5

output

短小精悍却烦人至深的题，我原先想的太简单了，写了个

	int n=0;	cin>>n;	for(int i=0;i<n scanf sort int modmax="0;" for i="0;" num>modmax; i++)		for(int j=i+1;num[j]>modmax && j<n j update num cout return>这样的东西……TLE的飞起……  <p></p>  <p>想了想就不能暴力啊，暴力的话剪枝也没用</p>  <h3 id="Code">Code：</h3>  <p></p>  <pre name="code" class="sycode">#include <cmath> #include <cctype>#include <cstdio>#include <string>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int n,a[200048]={0},ans=0;#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a) 0) update(a[p-1] % a[i]);			j+=a[i];		}		update(a[n-1] % a[i]); 	}	printf("%d\n",ans);	return 0;}</algorithm></iostream></cstring></cstdlib></string></cstdio></cctype></cmath>

E. Strange Sorting

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

How many specific orders do you know? Ascending order, descending order, order of ascending length, order of ascending polar angle... Let's have a look at another specific order: d-sorting. This sorting is applied to the strings of length at least d, where d is some positive integer. The characters of the string are sorted in following manner: first come all the 0-th characters of the initial string, then the 1-st ones, then the 2-nd ones and so on, in the end go all the (d?-?1)-th characters of the initial string. By the i-th characters we mean all the character whose positions are exactly i modulo d. If two characters stand on the positions with the same remainder of integer division byd, their relative order after the sorting shouldn't be changed. The string is zero-indexed. For example, for string 'qwerty':

Its 1-sorting is the string 'qwerty' (all characters stand on 0 positions),

Its 2-sorting is the string 'qetwry' (characters 'q', 'e' and 't' stand on 0 positions and characters 'w', 'r' and 'y' are on 1 positions),

Its 3-sorting is the string 'qrwtey' (characters 'q' and 'r' stand on 0 positions, characters 'w' and 't' stand on 1 positions and characters 'e' and 'y' stand on 2 positions),

Its 4-sorting is the string 'qtwyer',

Its 5-sorting is the string 'qywert'.

You are given string S of length n and m shuffling operations of this string. Each shuffling operation accepts two integer arguments kand d and transforms string S as follows. For each i from 0 to n?-?k in the increasing order we apply the operation of d-sorting to the substring S[i..i?+?k?-?1]. Here S[a..b] represents a substring that consists of characters on positions from a to b inclusive.

After each shuffling operation you need to print string S.

Input

The first line of the input contains a non-empty string S of length n, consisting of lowercase and uppercase English letters and digits from 0 to 9.

The second line of the input contains integer m ? the number of shuffling operations (1?≤?m·n?≤?106).

Following m lines contain the descriptions of the operations consisting of two integers k and d (1?≤?d?≤?k?≤?n).

Output

After each operation print the current state of string S.

Sample test(s)

input

qwerty34 26 35 2

output

qertwyqtewryqetyrw

Note

Here is detailed explanation of the sample. The first modification is executed with arguments k?=?4, d?=?2. That means that you need to apply 2-sorting for each substring of length 4 one by one moving from the left to the right. The string will transform in the following manner:

qwerty ?→? qewrty ?→? qerwty ?→? qertwy

Thus, string S equals 'qertwy' at the end of first query.

The second modification is executed with arguments k?=?6, d?=?3. As a result of this operation the whole string S is replaced by its 3-sorting:

qertwy ?→? qtewry

The third modification is executed with arguments k?=?5, d?=?2.

qtewry ?→? qertwy ?→? qetyrw

给一串字符串，每次给两个数字k和d，即要求从左到右每k个数进行一次 d-sorting，这种sorting的意思是，每d个数字选一个，这么分好组之后排序，详见hint

DIV2全场只有一个人（joker99）出了E，看了下代码暂时囫囵吞了下，贴一下代码等日后学习下。

Code：

#include <cmath> #include <cctype>#include <cstdio>#include <string>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)= 0; h--)                if (vl >= (1 = sh)	ps = pwr[h][ps - sh] + sh;                    vl -= (1   <br>  <br>  <p></p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p>  <p><br> </p> </algorithm></iostream></cstring></cstdlib></string></cstdio></cctype></cmath>

			2014-11-05 21:24:38	お知らせ	一般的なお知らせ ***** ロックの問題が修正されました。
一般的なお知らせ	ロックできない可能性があります。ハッキングの問題がいくつかあります。これはすぐに修正されます。 29	お知らせ	一般的なお知らせ	技術的な問題のため、テストの待ち時間は 30 分延長されます。引き続き他の問題を解決してください。ご迷惑をおかけして申し訳ありません。