Codeforces Round #264 (Div. 2)

现在的位置: 首页 > 综合 > 正文

Codeforces Round #264 (Div. 2)

2017年11月24日 ⁄ 综合 ⁄ 共 10134字 ⁄ 字号小中大 ⁄ 评论关闭

Caisa is going to have a party and he needs to buy the ingredients for a big chocolate cake. For that he is going to the biggest supermarket in town.

Unfortunately, he has just s dollars for sugar. But that's not a reason to be sad, because there are n types
of sugar in the supermarket, maybe he able to buy one. But that's not all. The supermarket has very unusual exchange politics: instead of cents the sellers give sweets to a buyer as a change. Of course, the number of given sweets always doesn't exceed 99,
because each seller maximizes the number of dollars in the change (100 cents can be replaced with a dollar).

Caisa wants to buy only one type of sugar, also he wants to maximize the number of sweets in the change. What is the maximum number of sweets he can get? Note, that Caisa doesn't want to minimize the cost of the sugar, he only wants to get maximum number of
sweets as change.

Input

The first line contains two space-separated integers n, s (1 ≤ n, s ≤ 100).

The i-th of the next n lines contains two integers xi, yi (1 ≤ xi ≤ 100; 0 ≤ yi < 100),
where xi represents
the number of dollars and yi the
number of cents needed in order to buy the i-th type of sugar.

Output

Print a single integer representing the maximum number of sweets he can buy, or -1 if he can't buy any type of sugar.

Sample test(s)

input
5 10
3 90
12 0
9 70
5 50
7 0

output
50

input
5 5
10 10
20 20
30 30
40 40
50 50

output
-1

Note

In the first test sample Caisa can buy the fourth type of sugar, in such a case he will take 50 sweets as a change.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
	int n,s,a,b;
	int ans=-1;
	cin>>n>>s;
	s=s*100;
	bool flag=false;
	for(int i=0;i<n;i++)
	{
		cin>>a>>b;
		int ts=s;
		if(ts>=a*100+b)
		{
			flag=true;
			ans=max(ans,0);
			if(b!=0)
				ans=max(ans,100-b);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Caisa solved the problem with the sugar and now he is on the way back to home.

Caisa is playing a mobile game during his path. There are (n + 1) pylons numbered from 0 to n in
this game. The pylon with number 0 has zero height, the pylon with number i (i > 0) has
height hi. The
goal of the game is to reach n-th pylon, and the only move the player can do is to jump from the current pylon (let's denote its number as k)
to the next one (its number will be k + 1). When the player have made such a move, its energy increases by hk - hk + 1 (if
this value is negative the player loses energy). The player must have non-negative amount of energy at any moment of the time.

Initially Caisa stand at 0 pylon and has 0 energy. The game provides
a special opportunity: one can pay a single dollar and increase the height of anyone pylon by one. Caisa may use that opportunity several times, but he doesn't want to spend too much money. What is the minimal amount of money he must paid to reach the goal
of the game?

Input

The first line contains integer n (1 ≤ n ≤ 105).
The next line contains n integers h1, h2, ..., hn (1 ≤ hi ≤ 105) representing
the heights of the pylons.

Output

Print a single number representing the minimum number of dollars paid by Caisa.

Sample test(s)

input
5
3 4 3 2 4

output
4

input
3
4 4 4

output
4

Note

In the first sample he can pay 4 dollars and increase the height of pylon with number 0 by 4 units.
Then he can safely pass to the last pylon.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,h[100100];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",h+i);
	int ans=h[1];
	int energy=0;
	for(int i=2;i<=n;i++)	
	{
		int deta=h[i-1]-h[i];
		if(deta>=0)
		{
			energy+=deta;
		}
		else
		{
			deta=-deta;
			if(energy>=deta)
			{
				energy-=deta;
			}
			else
			{
				int ca=deta-energy;
				ans+=ca;
				energy=0;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Gargari is jealous that his friend Caisa won the game from the previous problem. He wants to prove that he is a genius.

He has a n × n chessboard. Each cell of the chessboard has a number written on it. Gargari wants to place two bishops on the chessboard in such
a way that there is no cell that is attacked by both of them. Consider a cell with number x written on it, if this cell is attacked by one of the bishops
Gargari will get x dollars for it. Tell Gargari, how to place bishops on the chessboard to get maximum amount of money.

We assume a cell is attacked by a bishop, if the cell is located on the same diagonal with the bishop (the cell, where the bishop is, also considered attacked by it).

Input

The first line contains a single integer n (2 ≤ n ≤ 2000).
Each of the next n lines contains n integers aij (0 ≤ aij ≤ 109) —
description of the chessboard.

Output

On the first line print the maximal number of dollars Gargari will get. On the next line print four integers: x1, y1, x2, y2 (1 ≤ x1, y1, x2, y2 ≤ n),
where xi is
the number of the row where the i-th bishop should be placed, yi is
the number of the column where the i-th bishop should be placed. Consider rows are numbered from 1 to n from
top to bottom, and columns are numbered from 1 to n from left to right.

If there are several optimal solutions, you can print any of them.

Sample test(s)

input
4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1

output
12
2 2 3 2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;

int n;
LL a[2200][2200];
LL xie1[6000],xie2[6000];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)	
		{
			scanf("%I64d",&a[i][j]);
			xie1[i+j]+=a[i][j];
			xie2[i-j+3000]+=a[i][j];
		}
	}
	LL ans=0;int x1=1,y1=1,x2=1,y2=2;
	LL temp=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int id=j+i;
			if(id%2==1)
			{
				if(temp<=xie1[i+j]+xie2[i-j+3000]-a[i][j])	
				{
					temp=xie1[i+j]+xie2[i-j+3000]-a[i][j];
					x1=i;y1=j;
				}
			}
		}
	}
	ans+=temp;	
	temp=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int id=j+i;
			if(id%2==0)
			{
				if(temp<=xie1[i+j]+xie2[i-j+3000]-a[i][j])	
				{
					temp=xie1[i+j]+xie2[i-j+3000]-a[i][j];
					x2=i;y2=j;
				}
			}
		}
	}	
	ans+=temp;
	printf("%I64d\n %d %d %d %d\n",ans,x1,y1,x2,y2);
	return 0;
}

Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations.
Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can
you help Gargari?

You can read about longest common subsequence there:https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Input

The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5).
Each of the next k lines contains integers 1, 2, ..., n in
some order — description of the current permutation.

Output

Print the length of the longest common subsequence.

Sample test(s)

input
4 3
1 4 2 3
4 1 2 3
1 2 4 3

output
3

Note

The answer for the first test sample is subsequence [1, 2, 3].

预处理+简单DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int N,K;
int a[11][1100],be[11][1100][1100],before[1100][1100];
int dp[1100];

int main()
{
	scanf("%d%d",&N,&K);
	for(int i=1;i<=K;i++)
		for(int j=1;j<=N;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=K;i++)
	{
		for(int j=1;j<=N;j++)	
		{
			for(int k=1;k<j;k++)
			{
				be[i][a[i][k]][a[i][j]]=1;
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			bool flag=true;
			for(int k=1;k<=K;k++)	
			{
				if(be[k][i][j]==0)
				{
					flag=false; break;
				}
			}
			if(flag==true) before[i][j]=1;
		}
	}
	
	int ans=1;
	for(int i=1;i<=N;i++)
	{
		int c1=a[1][i];
		dp[c1]=1;
		for(int j=1;j<i;j++)
		{
			int c2=a[1][j];
			if(before[c2][c1])
			{
				dp[c1]=max(dp[c1],dp[c2]+1);
			}
		}
		ans=max(dp[c1],ans);
	}
	printf("%d\n",ans);
	return 0;
}
/*
4 3
1 4 2 3
4 1 2 3
1 2 4 3
*/

Caisa is now at home and his son has a simple task for him.

Given a rooted tree with n vertices, numbered from 1 to n (vertex 1 is
the root). Each vertex of the tree has a value. You should answer qqueries. Each query is one of the following:

Format of the query is "1 v". Let's write out the sequence of vertices along the path from the root to vertex v: u1, u2, ..., uk (u1 = 1; uk = v).
You need to output such a vertex ui that gcd(value of ui, value of v) > 1 and i < k.
If there are several possible vertices ui pick
the one with maximum value of i. If there is no such vertex output -1.
Format of the query is "2 v w". You must change the
value of vertex v to w.

You are given all the queries, help Caisa to solve the problem.

Input

The first line contains two space-separated integers n, q (1 ≤ n, q ≤ 105).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2·106),
where ai represent
the value of node i.

Each of the next n - 1 lines contains two integers xi and yi (1 ≤ xi, yi ≤ n; xi ≠ yi),
denoting the edge of the tree between vertices xi andyi.

Each of the next q lines contains a query in the format that is given above. For each query the following inequalities hold: 1 ≤ v ≤ n and 1 ≤ w ≤ 2·106. Note
that: there are no more than 50 queries that changes the value of a vertex.

Output

For each query of the first type output the result of the query.

Sample test(s)

input
4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

output
-1
1
2
-1
1

Note

gcd(x, y) is greatest common divisor of two integers x and y.

纯暴力,应为修改次数比较少,DFS预处理出所有的答案,每次有点跟新时就再预处理一次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

const int maxn=1001000;

int n,q;
int a[maxn/10];
vector<int> yushu[maxn/10];

void fenjie(int id,int x)
{
	yushu[id].clear();
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			yushu[id].push_back(i);
			while(x%i==0) x/=i;
		}
	}
	if(x!=1) yushu[id].push_back(x);
}

bool vis[2000100];
int prime[2000100],pr=1;

void get_prime()
{
	int t=1;
	bool flag=true;
	for(int i=2;i<=2000100;i+=t)
	{
		if(vis[i]==false)
		{
			prime[i]=pr++;
			for(int j=2;j*i<=2000100;j++)
				vis[j*i]=true;
		}
		if(flag==true) flag=false;
		else t=2;
	}
}

struct Edge
{
	int to,next;
}edge[200200];

int Adj[100100],Size=0;

void Add_Edge(int u,int v)
{
	edge[Size].to=v;
	edge[Size].next=Adj[u];
	Adj[u]=Size++;
}

void init()
{
	memset(Adj,-1,sizeof(Adj)); Size=0;
}

stack<int> stk[150000];
int ANS[100100];

int dist[100100];
void BFS()
{
	memset(vis,false,sizeof(vis));
	queue<int> q;
	q.push(1); vis[1]=true;

	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(int i=Adj[u];~i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(vis[v]==true) continue;
			vis[v]=true;
			dist[v]=dist[u]+1;
			q.push(v);
		}
	}
}

void DFS(int u,int fa)
{
	for(int i=Adj[u];~i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		int temp=-1,maxd=-(1<<30);
		for(int j=0,sz=yushu[v].size();j<sz;j++)	
		{
			if(stk[prime[yushu[v][j]]].size()>0)
			{
				int k=stk[prime[yushu[v][j]]].top();
				if(dist[k]>maxd)
				{
					maxd=dist[k];
					temp=k;
				}
			}
			stk[prime[yushu[v][j]]].push(v);
		}
		ANS[v]=temp;
		DFS(v,u);
		for(int j=0,sz=yushu[v].size();j<sz;j++)	
		{
			stk[prime[yushu[v][j]]].pop();
		}
	}
}

int main()
{
	get_prime();
	init();
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		fenjie(i,a[i]);
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		Add_Edge(u,v); Add_Edge(v,u);
	}
	Add_Edge(0,1);
	BFS();
	DFS(0,0);
	while(q--)
	{
		int k,a,b;
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%d",&a);
			printf("%d\n",ANS[a]);
		}
		else if(k==2)
		{
			scanf("%d%d",&a,&b);
			fenjie(a,b);
			DFS(0,0);
		}
	}
	return 0;
}

【上篇】TopCoder SAM 631 DIV2
【下篇】IT书籍阅读推荐

作者: captor

该日志由 captor 于6年前发表在综合分类下，最后更新于 2017年11月24日.
转载请注明: Codeforces Round #264 (Div. 2) | 学步园 +复制链接

抱歉!评论已关闭.

学步园

Codeforces Round #264 (Div. 2)

作者: captor

书签

最新文章New

本站推荐

返回首页