好多oj都崩掉了，于是打了cf。。
开始开的最后一题。。。尼玛题好长终于看完了。。。神题不会。。。。
I过了好多人。。看了下，一眼题。。。随便敲了下，1A
int a[];
int main(){
int n, k;
cin >> n >> k;
int tmp;
for (int i = ; i <= n; ++i) {
cin >> tmp;
a[tmp]++;
}
int ans = ;
for (int i = ; i <=k; ++i) {
if (a[i] > n/k) ans += a[i] - n/k;
}
cout << ans;
return ;
}
然后看J题。搜索，还是水题。1A
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
typedef long long ll;
using namespace std;
const int maxn = ;
int dir[][] = {-, , , , , , , -};
int n, m;
int mp[maxn][maxn][];
int vis[maxn][maxn];
char a[maxn][maxn];
int ans;
int dx(char ch) {
if (ch == 'U') return ;
if (ch == 'R') return ;
if (ch == 'D') return ;
if (ch == 'L') return ;
return -;
} bool check(int x, int y) {
if (x < n && x >= && y < m && y >= && a[x][y] != '*') return true;
return false;
} void dfs(int x, int y, int d) {
if (mp[x][y][d]) return ;mp[x][y][d] = ;
if (!vis[x][y]) {
//printf(">>%d %d\n", x, y);
vis[x][y] = ;
ans++;
}
//printf(">>%d %d %d\n", x, y, d); for (int i = ; i < ; ++i) {
int nx = x + dir[(d+i)%][];
int ny = y + dir[(d+i)%][];
//printf(">>>%d %d %d\n", nx, ny, (d+i)%4);
//if (mp[nx][ny][(d+i)%4]) return ;
if (check(nx, ny)) {
dfs(nx, ny, (d+i)%);
break;
}
}
} int main(){
cin >> n >> m;
for (int i = ; i < n; ++i) {
scanf("%s", a[i]);
}
int d;
int x, y;
for (int i = ; i < n; ++i) {
for (int j = ; j < m; ++j) {
if (dx(a[i][j]) >= ) {
vis[i][j] = ;
d = dx(a[i][j]);
x = i, y = j;
break;
}
}
}
//printf(">>%d %d %d\n", x, y, d);
ans = ;
for (int i = ; i < ; ++i) {
int nx = x + dir[(d+i)%][];
int ny = y + dir[(d+i)%][];
if (check(nx, ny)) {
dfs(nx, ny, (d+i)%);
break;
}
}
printf("%d\n", ans);
return ;
}
这是队友坑在了A题，wa了好久。。。我帮着看了一眼。。。。写的实在是太糟糕了。。。
我去搞F，数组开小了RE了几次。优先队列+二分做的。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = ; struct node {
int s, t;
int last;
int id;
bool operator < (const node rhs) const {
if (t == rhs.t) return last < rhs.last;
return t > rhs.t;
}
} a[N]; vector<int> f[];
int main(){
int n;
scanf("%d", &n);
int l = , r = ;
int ti = ;
for (int i = ; i < n; ++i) {
scanf("%d%d", &a[i].s, &a[i].t);
r = min(r, a[i].t-a[i].s);
ti = max(ti, a[i].t);
f[a[i].s].push_back(i);
a[i].id = i;
}
//printf(">>%d %d\n", r, ti);
int ans = ;
while (l <= r) {
int mid = (l+r)>>;
//printf("%d %d %d\n", l, r, mid);
priority_queue<node> que;
for (int i = ; i < n; ++i) a[i].last = mid;
bool fg = false;
for (int i = ; i < ti; ++i) {
//printf("t=%d\n", i);
if (f[i].size()) {
for (int j = ; j < f[i].size(); ++j) {
que.push(a[f[i][j]]);
}
}
if (que.size()) {
node tmp = que.top();//printf("tmp=%d\n", tmp.s);
if (tmp.t <= i) {
fg = true;
break;
}
if (--a[tmp.id].last == ) que.pop();
}
}
if (que.size() || fg) {
r = mid-;
} else{
l = mid+;
ans = mid;
}
}
printf("%d\n", ans*n);
return ;
}
然后队友去看D，我看A。。。由于是在看不懂队友的代码。。删掉重写的。。。
D貌似挺好写的，一会就A了。。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define PF(x) cout << "debug: " << x << " ";
#define EL cout << endl;
#define PC(x) puts(x);
typedef long long ll;
#define CLR(x, v) sizeof (x, v, sizeof(x))
using namespace std;
const int INF = 0x5f5f5f5f;
const int N= 2e5 + ;
const int mod=1e9 + ;
const int maxn = ;
const double eps = 1e-;
const double PI = acos(-1.0);
int t;
int sgn(double x){
if(fabs(x) < eps) return ;
if(x < ) return -;
else return ; }
struct Point{
double x,y;
Point() { }
Point(double _x,double _y){
x = _x,y = _y;
}
Point operator - (const Point &b) const{ //相对坐标
return Point(x - b.x,y - b.y);
}
double operator ^(const Point &b)const{//叉积
return x*b.y - y*b.x;
}
double operator *(const Point &b)const{//点积
return x*b.x + y*b.y;
}
void transXY(double B){
double tx = x,ty = y;
x = tx*cos(B) - ty*sin(B);
y = tx*sin(B) + ty*cos(B);
}
};
struct Line{
Point s,e;
Line() { }
Line (Point _s,Point _e){
s = _s,e = _e;
}
//两直线相交求交点
//第一个值为0表示直线重合，为1表示平行，为2是相交
//只有第一个值为2时交点才有意义
pair<int,Point> operator &(const Line &b) const{
Point res = s;
if(sgn((s-e)^(b.s-b.e)) == ){
if(sgn((s-b.e)^(b.s-b.e)) == )
return make_pair(,res);//重合
else
return make_pair(,res);
}
double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
res.x += (e.x-s.x)*t;
res.y += (e.y-s.y)*t;
return make_pair(,res);
}
};
double dist(Point a,Point b){
return sqrt((b-a)*(b-a));
}
bool Seg_inter_line(Line l1,Line l2){//判断直线l1与线段l2是否相交
return sgn((l2.s - l1.e) ^ (l1.s-l1.e)) * sgn((l2.e-l1.e)^(l1.s-l1.e)) <= ;
}
bool inter(Line l1,Line l2){
return max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= &&
sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= ; }
int n,ans[maxn];
Line line[maxn];
int main(){
// freopen("in.txt","r",stdin);
cin>>n;
double ts,s,f,tf;
for(int i = ;i <= n;i++){
scanf("%lf%lf%lf",&ts,&s,&f);
double max1,min1;
if(f <= s)
max1 = s,min1 =f;
else
max1 = f,min1 = s;
tf = (max1 - min1) + ts;
line[i] = Line(Point(ts,s),Point(tf,f));
}
for(int i = ;i <= n;i++)
for(int j = i+;j <= n;j++){
if(inter(line[i],line[j]))
ans[i]++,ans[j]++;
}
for(int i = ;i <= n;i++){
printf("%d",ans[i]);
if(i == n) printf("\n");
else printf(" ");
}
return ;
}
A题犯了几个sb错误，还好，改好之后就过了。。
#include <bits/stdc++.h>
using namespace std;
const int N = ; string a[N];
string login[N], domain[N];
bool bmail[N];
map<string, int> mp;
vector<int> ans[N]; int main() {
int n;
//freopen("in.txt","r",stdin);
cin >> n;
for (int i = ; i < n; ++i) {
cin >> a[i];
int p = a[i].find('@');
login[i] = a[i].substr(, p);
domain[i] = a[i].substr(p+, a[i].length()-p-);
transform(domain[i].begin(), domain[i].end(), domain[i].begin(), ::tolower);
if (domain[i] == "bmail.com") bmail[i] = ;
}
for (int i = ; i < n; ++i) {
if (bmail[i]) {
int p = login[i].find('+');
login[i] = login[i].substr(, p);
for (string::iterator it = login[i].begin(); it != login[i].end(); ++it)
{
if ( *it == '.')
{
login[i].erase(it);
--it;
}
}
}
transform(login[i].begin(), login[i].end(), login[i].begin(), ::toupper);
//cout << login[i] << " " << domain[i] << endl;
}
int cnt = ;
for (int i = ; i < n; ++i) {
string tmp = login[i]+domain[i];
//cout << tmp << endl;
if (mp[tmp] == ) mp[tmp] = cnt++;
ans[mp[tmp]].push_back(i);
}
cout << cnt- << endl;
for (int i = ; i < cnt; ++i) {
cout << ans[i].size();
for (int j = ; j < ans[i].size(); ++j) {
cout << " " << a[ ans[i][j] ];
}
cout << endl;
} return ;
}
然后队友B有了思路。。写了下，也过了。。。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define PF(x) cout << "debug: " << x << " ";
#define EL cout << endl;
#define PC(x) puts(x);
typedef long long ll;
#define CLR(x, v) sizeof (x, v, sizeof(x))
using namespace std;
const int INF = 0x5f5f5f5f;
const int maxn = ;
const int mod = 1e9 + ;
const double eps = acos(-);
const double PI= atan(1.0)*;
int n,bx[maxn],tree[maxn],sum[maxn];
struct st{
int a,b;
}re[maxn];
map<int,int>q;
bool cmp(st x,st y){
return x.a<y.a;
}
void Add(int k , int num)
{
while(k <= n)
{
tree[k] += num;
k += k&(-k);
}
}
int Sum(int k)
{
int sum = ;
while(k > )
{
sum += tree[k];
k -= k&(-k);
}
return sum;
}
int main(){
// freopen("in.txt","r",stdin);
cin>>n;
int t1,t2;
for(int i = ;i <= n;i++){
scanf("%d%d",&t1,&t2);
if(t1 > t2)
swap(t1,t2);
re[i].a = t1;
re[i].b = t2;
//cout<<re[i].a<<" "<<re[i].b<<endl;
bx[i] = re[i].b;
}
sort(re+,re++n,cmp);
sort(bx+,bx++n);
int num = bx[],cnt = ;
q[bx[]] = ,sum[]++;
for(int i = ;i <= n;i++){
if(bx[i] != num){
Add(cnt,sum[cnt]);
cnt++;
q[bx[i]] = cnt;
num = bx[i];
sum[cnt]++;
// cout<<cnt<<" "<<bx[i]<<endl;
}
else
sum[cnt]++;
}
Add(cnt,sum[cnt]);
ll s = ,x,y;
//for(int i = 1;i <= cnt;i++)
// cout<<i<<" "<<Sum(i)<<endl;
for(int i = ;i <= n;i++){
//cout<<Sum(i)<<endl;
for(int j = i;j <= n;j++){
int k = Sum(cnt)-Sum(q[re[j].b]-);
ll sx = (ll)k*re[i].a*re[j].b;
// cout<<re[i].a<<" "<<re[j].b<<endl;
if(s < sx){
s = sx;
x = re[i].a;
y = re[j].b;
}
// cout<<s<<endl;
//cout<<x<<" "<<y<<endl;
}
Add(q[re[i].b],-);
}
printf("%lld\n",s);
cout<<x<<" "<<y<<endl;
//printf("%d %d\n",x,y);
return ;
}
这时我比较累了，不想看题，ys看完G题，我们仨讨论下，没什么结果，这时候时间也差不多了，剩几分钟。。。于是就撤了。。
感觉比亚洲区域赛简单（当然，难题还是很难的。。。。）
还是继续加油啊 太慢了 后面都没时间了。。。