A，B两题就不写了。。。
1 second
256 megabytes
standard input
standard output
Recently Pashmak has been employed in a transportation company. The company has k buses and has a contract with a school which has n students.
The school planned to take the students to d different places for d days
(each day in one place). Each day the company provides all the buses for the trip. Pashmak has to arrange the students in the buses. He wants to arrange the students in a way that no two students become close friends. In his ridiculous idea, two students will
become close friends if and only if they are in the same buses for all d days.
Please help Pashmak with his weird idea. Assume that each bus has an unlimited capacity.
The first line of input contains three space-separated integers n, k, d (1 ≤ n, d ≤ 1000; 1 ≤ k ≤ 109).
If there is no valid arrangement just print -1. Otherwise print d lines,
in each of them print n integers. The j-th integer
of the i-th line shows which bus the j-th student
has to take on the i-th day. You can assume that the buses are numbered from 1 to k.
3 2 2
1 1 2 1 2 1
3 2 1
-1
Note that two students become close friends only if they share a bus each day. But the bus they share can differ from day to day.
分析：即给定n个学生,k俩车，要旅行d天，给每个学生安排车号，每辆车能容纳无穷多人，要求任何两人在d天中的安排不是一模一样，思路，假设k=3,d = 3,即有三俩车，要旅行三天，那么第一个学生的车号可以是111，第二个学生的车号可以是112，然后接着113，121，122，123，131.。。。因为n,d<1000，所以当k>9的时候，可以把k认为是9，因为上述的组合足以给出不同的1000个组合了。
比赛时代码写的有点乱。。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;
const int N=1100;
char arr[N][N];
int n,k,d;
int main()
{
while(cin>>n>>k>>d)
{
if(k==1)
{
if(d>1)
{
if(n>1)
cout<<-1<<endl;
else
{
for(int i=0;i<d;i++)
cout<<1<<endl;
}
}
else
{
if(n==1)
{
cout<<1<<endl;
}
else
cout<<-1<<endl;
}
}
else
{
if(d==1)
{
if(k<n)
cout<<-1<<endl;
else
{
for(int i=1;i<=n;i++)
cout<<i<<" ";
cout<<endl;
}
continue;
}
string s = "";
for(int i=0;i<d;i++)
s+="1";
bool flag = true;
int j=1;
for(;j<=n;j++)
{
for(int i=1;i<=d;i++)
{
arr[i][j] = s[i-1];
}
int end = s.length()-1;
char c = '9';
if(k>9)
c = '9';
else
c = k+'0';
while(end>=0&&s[end]==c)
end--;
if(end==-1)
{
flag=false;
break;
}
else
{
int p = (s[end]-'0') +1;
s[end] = (char)(p+'0');
end++;
while(end<s.length())
s[end++] = '1';
}
}
if(!flag&&j<n)
{
cout<<-1<<endl;
continue;
}
for(int i=1;i<=d;i++)
{
for(int j=1;j<=n;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
}
return 0;
}
分析：首先肯定可以做预处理，记录f(1,i,x)和f(i,n,x)分别表示下标从1-i和下标从i-n的字数组中和x值相同的个数，这里我用temp1和temp2表示，题目的意思即求这样的组合(i,j)满足i<j 并且temp1[i]> temp2[j], 直接两层循环是超时的，故需要优化，仔细一看，这不和求逆序对差不多嘛，那优化方法也肯定类似，采用分治法，先divide成两部分，分别求得两部分的值，然后左边部分的下标肯定小于右边部分的下标，俩部分分别排下序，就可以轻松找出逆序对的个数了。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;
const int N=2000000;
int arr[N];
int temp1[N];
int temp2[N];
#define mid (l+r)/2
typedef long long ll;
int n;
ll solve(int l,int r)
{
if(l>=r)
return 0;
if(l==r-1)
{
if(temp1[l]>temp2[r])
return 1;
else
return 0;
}
ll ret1 = solve(l,mid);
ll ret2 = solve(mid+1,r);
vector<int> v1;
vector<int> v2;
for(int i=l;i<=mid;i++)
v1.push_back(temp1[i]);
for(int i=mid+1;i<=r;i++)
v2.push_back(temp2[i]);
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end(),greater<int>());
int start1 = 0;
int start2 = v2.size()-1;
while(start1<v1.size()&&v1[start1]<=v2[start2])
start1++;
ll ret = ret1+ret2;
while(start1<v1.size())
{
while(v1[start1]>v2[start2]&&start2>=0)
start2--;
ret+=(v2.size()-1-start2);
start1++;
}
return ret;
}
int main()
{
cin>>n;
map<int,int> m1;
map<int,int> mn;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
m1[arr[i]]++;
temp1[i] = m1[arr[i]];
}
for(int i=n;i>=1;i--)
{
mn[arr[i]]++;
temp2[i] = mn[arr[i]];
}
ll ret = 0;
ret = solve(1,n);
cout<<ret<<endl;
return 0;
}
1 second
256 megabytes
standard input
standard output
Pashmak's homework is a problem about graphs. Although he always tries to do his homework completely, he can't solve this problem. As you know, he's really weak at graph theory; so try to help him in solving the problem.
You are given a weighted directed graph with n vertices and m edges.
You need to find a path (perhaps, non-simple) with maximum number of edges, such that the weights of the edges increase along the path. In other words, each edge of the path must have strictly greater weight than the previous edge in the path.
Help Pashmak, print the number of edges in the required path.
The first line contains two integers n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ min(n·(n - 1), 3·105)).
Then, m lines follows. The i-th line contains three
space separated integers: ui, vi, wi (1 ≤ ui, vi ≤ n; 1 ≤ wi ≤ 105) which
indicates that there's a directed edge with weight wifrom
vertex ui to
vertex vi.
It's guaranteed that the graph doesn't contain self-loops and multiple edges.
Print a single integer — the answer to the problem.
3 3 1 2 1 2 3 1 3 1 1
1
3 3 1 2 1 2 3 2 3 1 3
3
6 7 1 2 1 3 2 5 2 4 2 2 5 2 2 6 9 5 4 3 4 3 4
6
In the first sample the maximum trail can be any of this trails: 
.
In the second sample the maximum trail is 
.
In the third sample the maximum trail is 
.
分析：因为边的权值需要从小到大，那么自然而然的第一步就是对边按权值从小到大排序。用dp[i]表示路径中介点为i时的最大边数，然后从小到大处理权值递增的边，每次需要处理一批（因为边权值要严格递增），转移方程为dp[edge[i]].to] = max(dp[edge[i]].to,dp[edge[i]].from+1)
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
using namespace std;
const int N=410000;
int n,m;
struct edge
{
int from;
int to;
int weight;
}edges[N];
bool cmp(edge e1,edge e2)
{
return e1.weight<e2.weight;
}
int dp[N];
int f[N];
int main()
{
while(cin>>n>>m)
{
memset(dp,0,sizeof(dp));
memset(f,0,sizeof(f));
for(int i=0;i<m;i++)
{
cin>>edges[i].from>>edges[i].to>>edges[i].weight;
}
sort(edges,edges+m,cmp);
for(int i=0;i<m;i++)
{
int j=i;
while(j<m&&edges[j].weight==edges[i].weight)
j++;
for(int k=i;k<j;k++)
{
f[edges[k].to] = max(f[edges[k].to],dp[edges[k].from]+1);
}
for(int k=i;k<j;k++)
dp[edges[k].to] = f[edges[k].to];
i = j-1;
}
int ans = 0;
for(int i=1;i<=n;i++)
ans = max(ans,dp[i]);
cout<<ans<<endl;
}
return 0;
}
感动。。。终于tc和cf又都打回div1了。。。