CF 659 A方向 B排序 C暴力 D方向 E并查集/无向环的dfs/无向环的染色bfs F并查集+dfs/bfs G：递推

Vasya lives in a round building, whose entrances are numbered sequentially by integers from 1 to n. Entrance n and entrance 1 are adjacent.

Today Vasya got bored and decided to take a walk in the yard. Vasya lives in entrance a and he decided that during his walk he will move around the house b entrances in the direction of increasing numbers (in this order entrance n should be followed by entrance 1). The negative value of b corresponds to moving |b| entrances in the order of decreasing numbers (in this order entrance 1 is followed by entrance n). If b = 0, then Vasya prefers to walk beside his entrance.

Illustration for n = 6, a = 2, b =  - 5.

Help Vasya to determine the number of the entrance, near which he will be at the end of his walk.

#includeusing namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int main(){
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
while (abs(b) > n){
if (b > 0) b -= n;
else b += n;
}
int tmp = a + b;
while (abs(tmp) > n){
if (tmp > 0) tmp -= n;
else tmp += n;
}
if (tmp <= 0) printf("%d\n", n+tmp);
else printf("%d\n", tmp);
return 0;
}

Very soon Berland will hold a School Team Programming Olympiad. From each of the m Berland regions a team of two people is invited to participate in the olympiad. The qualifying contest to form teams was held and it was attended by n Berland students. There were at least two schoolboys participating from each of the m regions of Berland. The result of each of the participants of the qualifying competition is an integer score from 0 to 800 inclusive.

The team of each region is formed from two such members of the qualifying competition of the region, that none of them can be replaced by a schoolboy of the same region, not included in the team and who received a greater number of points. There may be a situation where a team of some region can not be formed uniquely, that is, there is more than one school team that meets the properties described above. In this case, the region needs to undertake an additional contest. The two teams in the region are considered to be different if there is at least one schoolboy who is included in one team and is not included in the other team. It is guaranteed that for each region at least two its representatives participated in the qualifying contest.

Your task is, given the results of the qualifying competition, to identify the team from each region, or to announce that in this region its formation requires additional contests.

#includeusing namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct body{
string name;
int num;
};
int n, m;
vector  a[10000 + 5];
bool cmp(const body x, const body y){
return x.num > y.num;
}
int main(){
while (scanf("%d%d", &n, &m) == 2){
for (int i = 0; i < n; i++){
body tmp;
int p;
cin >> tmp.name >> p >> tmp.num;
a[p].push_back(tmp);
}
for (int i = 1; i <= m; i++){
sort(a[i].begin(), a[i].end(), cmp);
int tmp = a[i].size();
if (tmp >= 3){
if (a[i][1].num == a[i][2].num ){
printf("?\n");
continue;
}
else {
cout << a[i][0].name << " " << a[i][1].name << endl;
}
}
else if (tmp == 2){
cout << a[i][0].name << " " <<< endl;
}
else printf("?\n");
a[i].erase(a[i].begin(), a[i].end());
}
}
return 0;
}

In Berland recently a new collection of toys went on sale. This collection consists of 109 types of toys, numbered with integers from 1 to109. A toy from the new collection of the i-th type costs i bourles.

Tania has managed to collect n different types of toys a1, a2, ..., an from the new collection. Today is Tanya's birthday, and her mother decided to spend no more than m bourles on the gift to the daughter. Tanya will choose several different types of toys from the new collection as a gift. Of course, she does not want to get a type of toy which she already has.

Tanya wants to have as many distinct types of toys in her collection as possible as the result. The new collection is too diverse, and Tanya is too little, so she asks you to help her in this.

#includeusing namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
vector a;
int n, m;
/*
int cal(int m){
double t = sqrt(8 * m + 1);
return (t - 1) / 2;
}
*/
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
a.push_back(x);
}
sort(a.begin(), a.end());
int cnt = 0, sum = 0;
int d = 0;
vector ind;
for (int i = 1; sum + i <= m; i++){
if (i == a[d]){
d++;
continue;
}
cnt++;
sum += i;
ind.push_back(i);
}
printf("%d\n", cnt);
for (int i = ind.size() - 1; i >= 0; i--){
printf("%d%c", ind[i], i == 0 ? '\n' : ' ');
}
return 0;
}

Maria participates in a bicycle race.

The speedway takes place on the shores of Lake Lucerne, just repeating its contour. As you know, the lake shore consists only of straight sections, directed to the north, south, east or west.

Let's introduce a system of coordinates, directing the Ox axis from west to east, and the Oy axis from south to north. As a starting position of the race the southernmost point of the track is selected (and if there are several such points, the most western among them). The participants start the race, moving to the north. At all straight sections of the track, the participants travel in one of the four directions (north, south, east or west) and change the direction of movement only in bends between the straight sections. The participants, of course, never turn back, that is, they do not change the direction of movement from north to south or from east to west (or vice versa).

Maria is still young, so she does not feel confident at some turns. Namely, Maria feels insecure if at a failed or untimely turn, she gets into the water. In other words, Maria considers the turn dangerous if she immediately gets into the water if it is ignored.

Help Maria get ready for the competition — determine the number of dangerous turns on the track.

#includeusing namespace std;
vector d;
vector > vec;
int main(){
int n;
scanf("%d", &n);
while (n--){
int a, b;
scanf("%d%d", &a, &b);
vec.push_back(make_pair(a, b));
}
int l = vec.size();
for (int i = 0; i < l-1; i++){
int cnt = 0;
int x = vec[i+1].first;
int y = vec[i+1].second;
if (vec[i].first == x && vec[i].second < y) cnt = 0;
else if (vec[i].first == x && vec[i].second > y) cnt = 2;
else if (vec[i].second == y && vec[i].first < x) cnt = 1;
else cnt = 3;
d.push_back(cnt);
}
l = d.size();
int cnt = 0;
for (int i = 0; i < l-1; i++){
int now = d[i];
int next = d[i+1];
int tmp = (now + 3) % 4;
if (next == tmp) cnt++;
}
printf("%d\n", cnt);
return 0;
}

#includeusing namespace std;
const int maxn = 100000 + 5;
int n, m;
bool used[maxn];
int par[maxn];
int edge, cnt;
int x[maxn];
int a[maxn], b[maxn];
int sear(int x){
if (par[x] == x) return x;
return par[x] = sear(par[x]);
}
void unite(int x, int y){
x = sear(x);
y = sear(y);
if (x == y) return ;
if (x < y){
par[y] = x;
}
else par[x] = y;
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
par[i] = i;
}
bool flag = 0;
edge = cnt = 0;
for (int i = 1; i <= m; i++){
int v;
scanf("%d%d", x + i, &v);
unite(x[i], v);
}
for (int i = 1; i <= n; i++){
a[sear(i)]++;
}
for (int i = 1; i <= m; i++){
b[sear(x[i])]++;
}
int ans = 0;
for (int i = 1; i <= n; i++){
if (b[i] == a[i]-1) ans++;
}
printf("%d\n", ans);
return 0;
}

#includeusing namespace std;
const int maxn = 1000 + 5;
typedef long long ll;
int n, m, cnt;
ll lim;
int l[maxn * maxn];
int par[maxn * maxn], vis[maxn][maxn];
vector > vec;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1 ,1};
struct point{
int x, y;
int val;
bool operator < (const point &p) const{
return val > p.val;
}
}atlas[maxn * maxn];
int findp(int x){
if (par[x] == x) return x;
return par[x] = findp(par[x]);
}
void dfs(int x, int y){
if (vis[x][y] == 0) return ;
vis[x][y] = 0;
vec.push_back(make_pair(x, y));
for (int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny])
dfs(nx, ny);
}
}
void solve(){
ll res = -1;
int lo = 0;
int a, b;
for (int i = 0; i < n * m; i++){
int x = atlas[i].x;
int y = atlas[i].y;
vis[x][y] = 1;
for (int j = 0; j < 4; j++){
//printf("haha\n");
int nx = x + dx[j];
int ny = y + dy[j];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny] == 0) continue;
a = findp(x * m + y);
b = findp(nx * m + ny);
if (b != a){
par[b] = a;
l[a] += l[b];
}
}
if (lim % atlas[i].val == 0 && l[x * m + y] >= lim / atlas[i].val){
dfs(x, y);
res = atlas[i].val;
lo = lim / atlas[i].val;
break;
}
}
if (res == -1){
printf("NO\n");
return ;
}
else printf("YES\n");
memset(vis, 0, sizeof(vis));
for (int i = 0; i < lo; i++){
int x = vec[i].first, y = vec[i].second;
vis[x][y] = 1;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (vis[i][j]) printf("%d", res);
else printf("%d", 0);
printf("%c", j == m-1 ? '\n' : ' ');
}
}
}
void init(){
scanf("%d%d%I64d", &n, &m, &lim);
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
int tmp;
scanf("%d", &tmp);
atlas[i*m + j].x = i;
atlas[i*m + j].y = j;
atlas[i*m + j].val = tmp;
}
}
sort(atlas, atlas + n * m);
for (int i = 0; i < n * m; i++){
par[i] = i;
l[i] = 1;
}
}
int main(){
init();
solve();
return 0;
}

Long ago, Vasily built a good fence at his country house. Vasily calls a fence good, if it is a series of n consecutively fastened vertical boards of centimeter width, the height of each in centimeters is a positive integer. The house owner remembers that the height of thei-th board to the left is hi.

Today Vasily decided to change the design of the fence he had built, by cutting his top connected part so that the fence remained good. The cut part should consist of only the upper parts of the boards, while the adjacent parts must be interconnected (share a non-zero length before cutting out of the fence).

You, as Vasily's curious neighbor, will count the number of possible ways to cut exactly one part as is described above. Two ways to cut a part are called distinct, if for the remaining fences there is such i, that the height of the i-th boards vary.

As Vasily's fence can be very high and long, get the remainder after dividing the required number of ways by 1 000 000 007 (109 + 7).

#includeusing namespace std;
typedef long long ll;
const int maxn = 1000000 + 5;
const ll inf = 0x3f3f3f3f;
const ll mod = 1000000007;
ll n;
ll h[maxn];
ll s[maxn];
int main(){
while (scanf("%I64d", &n) == 1){
memset(h, 0, sizeof(h));
for (int i = 1; i <= n; i++){
scanf("%I64d", h + i);
h[i]--;
}
ll res = 0;
memset(s, 0, sizeof(s));
for (int i = 1; i <= n; i++){
s[i + 1] = (s[i] * min(h[i - 1], min(h[i], h[i + 1])) + min(h[i], h[i + 1])) % mod;
res = (res + s[i + 1] * min(h[i], h[i + 1])) % mod;
}
for (int i = 1; i <= n; i++){
res += h[i];
res %= mod;
}
printf("%I64d\n", res);
}
return 0;
}