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

Codeforces Round #261 (Div. 2)

2018年02月23日 ⁄ 综合 ⁄ 共 4303字 ⁄ 字号 评论关闭

A. Pashmak and Garden

题意:一个平行于坐标轴的正方形,给两个顶点,求另外两个顶点?

题解:判断下给的两个点连城的直线是不是平行坐标轴。平行,另外两个点就是平移一个变长后的位置。不平行,看x轴和y轴距离是否相等,不想等不存在。

B. Pashmak and Flowers

题意:给一组数据,取两个数,求使得这两个数的差值最大的取法有多少种?

题解:求出最大的数有多少个,最小的数有多少个,两个数的乘积就是所有取法。特判的是全都一样的情况。

C. Pashmak and Buses

题意:有n个同学,乘坐k量客车去旅游d天。如果两个人d天都在一起(每次都做同一辆车),那么他们变成好朋友。求没有好朋友的分配方法。

题解:可以把每个小朋友d天所乘坐的车号放在一起看成一个共d位的k进制数。只要任意两个同学的d位k进制数不一样就可以。比赛的时候没有想到这么做,听人家说完思路后代码很容易实现。

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
const int maxn = 1010;
ll n, k, d;
int ans[maxn][maxn];
int base[maxn];
int main(){
	while(cin >> n >> k >> d){
		int flag = 0;
		for(int i = 0; i < d; i ++) base[i] = 1;
		for(int i = 0; i < n; i ++){
			if( base[0] > k ) {
				cout << -1 << endl;
				flag = 1;
				break;
			}
			for(int j = 0; j < d; j ++) ans[j][i] = base[j];
			base[d-1] ++;
			int t = d-1;
			while(t > 0 && base[t] > k){
				base[t] = 1;
				t--;
				base[t] ++;
			}
			
		}
		if( flag ) continue;
		for(int i = 0; i < d; i ++){
			for(int j = 0; j < n-1; j ++)
				cout << ans[i][j] << ' ';
			cout << ans[i][n-1] << endl;
		}
	}
	return 0;
}

D. Pashmak and Parmida's
problem

题意:函数F(I, J, X)  表示统计下从I到J中X出现的次数。给一个数列,求满足F(1, I, A[I]) > F(J, N, A[J])的i和j有多少组?

题解:预处理出每个F(J, N, A[J]), 然后对于每个J求出J前面的F(1, I, A[I])的个数。F(1, i, A[I])用树状数组维护求前缀和。

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
int a[1000010], b[1000010], c[1000010];
int num[1000010];

template <int SZ>  
class BIT{  
    long long c[SZ+10];  
public :  
    void clear(){clr(c,0);}  
    long long getsum(int x){  
        long long s=0;  
        while(x>0)  
            s+=c[x], x-=x&-x;  
        return s;  
    }  
    void update(int x, int n){  
        while(x<=SZ)  
            c[x]+=n,x+=x&-x;  
    }  
}; 
BIT<1000010> bit;
int main(){
	int n;
	while(~scanf("%d",&n)){
		bit.clear();
		for(int i = 0; i < n; i ++){
			scanf("%d",a+i);
			b[i] = a[i];
		}
		sort(b, b+n);
		int size = unique(b, b+n) - b;
		for(int i = 0; i < n; i ++) a[i] = lower_bound(b,b+size,a[i]) - b+1;
//		for(int i = 0; i < n; i ++) cout << a[i] << ' '; cout << endl;
		memset(num, 0, sizeof(num));
		for(int i = 0; i < n; i ++) {
			num[a[i]] ++;
			b[i] = num[a[i]];
		}
		memset(num, 0, sizeof(num));
		for(int i = n-1; i >= 0; i --){
			num[a[i]] ++;
			c[i] = num[a[i]];
		}
		bit.update(b[0],1);
		ll ans = 0;
		for(int i = 1; i < n; i ++){
			int k = c[i];
			int vel = bit.getsum(k);
			ans += i-vel;
//			cout << k << ' ' << vel << ' ' << i << endl;
			bit.update(b[i],1);
		}
		cout << ans << endl;
	}
	return 0;
}

E.
Pashmak and Graph

题意:给一个图,求一条最长的链满足链上的边的长度是严格递增的。

题解:比赛的时候没时间写,结束看了下,有点想法。将所有的边排序,从前面开始去遍历每条边推出下一条边的长度。邻接表求下一条边的时候TLE了,就不会了。也是看的网上的思路,将当前最大值存起来就可以了,实现起来还可以。

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
const int maxn = 300010;
const int maxv = maxn;
int n, m;
struct Edge{
	int to, vel, num,from;
	bool operator < (const Edge& a) const{
		return vel < a.vel;
	}
};
Edge edge[maxv];
vector<Edge> GB[maxn];
int ans[maxn];
struct node{
	int x, vel, lx;
} ma[maxn]; 
int main(){
	int from, to, vel, num;
	int t_vel, t_num;
	while(~scanf("%d%d",&n,&m)){
//		for(int i = 0; i <= n; i ++) G[i].clear();
		memset(ans, 0, sizeof(ans));
		memset(ma, 0, sizeof(ma));
		for(int i = 0; i < m; i ++){
			scanf("%d%d%d",&from,&to,&vel);
			edge[i].num = i;
			edge[i].to = to;
			edge[i].vel = vel;
			edge[i].from = from;
			GB[to].push_back((Edge){from,vel,i,to});
		}
		sort(edge, edge+m);
//		for(int i = 0; i < m; i ++) cout << edge[i].vel << ' ' << edge[i].num << endl;
		int out = 0;
		for(int i = 0; i < m; i ++){
			from = edge[i].from;
			to = edge[i].to;
			vel = edge[i].vel;
			num = edge[i].num;
			if( vel > ma[from].vel) ans[num] = ma[from].x + 1;
			else ans[num] = ma[from].lx + 1;
			if( ma[to].x < ans[num]){
				if( vel > ma[to].vel ) {
					ma[to].lx = ma[to].x;
					ma[to].vel = vel;
					ma[to].x = ans[num];
				}
				else ma[to].x = ans[num];
			}
			out = max(out, ans[num]);
		}
//		for(int i = 0; i < n; i ++) cout << ans[i] << ' '; cout << endl;
		printf("%d\n",out);
	}
	return 0;
}

ps:有好多想法都想不到,代码的正确率也好低……太弱了……

抱歉!评论已关闭.