题意:一个平行于坐标轴的正方形,给两个顶点,求另外两个顶点?
题解:判断下给的两个点连城的直线是不是平行坐标轴。平行,另外两个点就是平移一个变长后的位置。不平行,看x轴和y轴距离是否相等,不想等不存在。
题意:给一组数据,取两个数,求使得这两个数的差值最大的取法有多少种?
题解:求出最大的数有多少个,最小的数有多少个,两个数的乘积就是所有取法。特判的是全都一样的情况。
题意:有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; }
题意:给一个图,求一条最长的链满足链上的边的长度是严格递增的。
题解:比赛的时候没时间写,结束看了下,有点想法。将所有的边排序,从前面开始去遍历每条边推出下一条边的长度。邻接表求下一条边的时候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:有好多想法都想不到,代码的正确率也好低……太弱了……