在hosts文件append一个173.194.65.108 imap.gmail.com
173.194.65.108 pop.gmail.com 173.194.65.108 imap.gmail.com 173.194.193.108 smtp.gmail.com
33% Informatics & 33% Physics & 33% Mathematics
2015年3月05日 17:00
在hosts文件append一个173.194.65.108 imap.gmail.com
173.194.65.108 pop.gmail.com 173.194.65.108 imap.gmail.com 173.194.193.108 smtp.gmail.com
2014年10月28日 00:09
失眠者自有失眠者的享受,失忆者自有失忆者的幸福。我多么希望自己不仅是一个失眠者啊。
2014年5月29日 22:01
网上关于FFT的介绍很多,算导也有相关算法描述,但是原来读的时候很清楚,可是读完也不知道怎么实现.这次在机房膜拜了大神的代码后自己琢磨了一个初等数学描述的证明,并得到了一个比较简洁的实现方法.主要是For OIer,所以给出的证明是简洁而不失于严谨性的(融合了算导, 维基百科的证明和自己的理解).
2014年4月28日 20:19
悲剧的ubuntu14.04折磨了我近四天了。一开始是13.10看见14.10还是LTS版本,就打算更新一下呗,不出所料,更新完黑屏了。可能是显卡驱动出现了问题吧。折腾两天后终于信邪,从命令行拷出个人文件后,在win7删除卷了。下了一个14.04映像,用FreeBSD引导一下,本以为这就万事大吉了,可谁知这才是噩梦的开始。周日早上重启电脑,进入grub rescue模式,手头又没有引导盘,急了一上午,下午找cui1997借了一张win7 Professional引导盘,可是我家的电脑是win7 Home Basic,本以为不成呢。shift+F10打开命令行,敲入bootrec /fixmbr即可重启。终于成功进入ubuntu安装。安装后,发现自带的IBUS输入法太坑了,需要用一个辅音代替一个长于一个字母的元音,用一个元音代替长于一个字母的辅音。今天这才刚刚发现搜狗输入法其实很容易安装,直接到官网下载,双击那个deb包即可。到语言支持那里修改键盘输入方式系统为fcitx,再重启即可。安装truecrypt也很容易,下载一下那个.tar.gz文件,解压后用./执行即可。
2014年4月22日 13:56
这一年的天津省选出的题还是比较复杂的,而Day2的题或许还好吧。
这第一题还算好做,只要想出了关于时间建立树状数组即可,当然运用可持久化线段树也未尝不可。具体细节看代码吧,只要想清楚了三十分钟应该能调对。需要注意的是打爆了防御的那次攻击,伤害值并不会翻倍,哪怕在这一次开始前攻击力已经大于防御力了也不会使伤害值翻倍。
#include<cstdio> #include<cstdlib> #include<algorithm> #include<vector> using namespace std; #define maxn 200005 #define base 1000000009 #define lowbit(x) ((x)&(-(x))) vector<pair<int,int> > q; vector<pair<pair<int,int>,int> > a; int p[maxn],n,nq,s[maxn],ans; void insert(int w,int x){ while(w < maxn){ s[w] += x; w += lowbit(w); } } int sum(int w){ int ret = 0; while(w){ ret += s[w]; w -= lowbit(w); } return ret; } int main(){ freopen("defense.in","r",stdin); freopen("defense.out","w",stdout); scanf("%d%d",&n,&nq); for(int i = 1;i<=n;i++) scanf("%d",&p[i]); scanf("\n"); for(int i = 1;i<=nq;i++){ char c; scanf("%c",&c); if(c == 'A'){ int l,r,x; scanf("%d%d%d\n",&l,&r,&x); a.push_back(make_pair(make_pair(l,i),x)); a.push_back(make_pair(make_pair(r+1,i),-x)); } else{ int x; scanf("%d\n",&x); q.push_back(make_pair(x,i)); } } sort(a.begin(),a.end()); sort(q.begin(),q.end()); vector<pair<pair<int,int>,int> >::iterator aw = a.begin(); for(int i = 0;i<q.size();i++){ while(aw < a.end() && (*aw).first.first <= q[i].first){ insert((*aw).first.second,(*aw).second); aw++; } int l = 0,r = q[i].second; while(l < r){ int m = (l + r) >> 1; if(sum(m) >= p[q[i].first]) r = m; else l = m + 1; } int ret = (2*sum(q[i].second) - sum(l))%base; ans = (ans + ret) % base; } printf("%d\n",ans); return 0; }
第三题需要稍微动一下脑筋,第一个发现的是如果对于一个点,满足题设的点们应该分布在以之为中心的一个倾斜[tex]\frac{\pi}{4}[/tex]角度的一个正方形内部,由此想到将其转过来,变成我们通常看到的正方形那样。即对点(x,y)→(x+y,x-y),继续思考发现,我们只需将这些新点按照x坐标排序,然后扫一遍,找到在其上方和下方刚刚扫过的点中离它最近的两个点。判断这两个点的纵坐标与之相差是否小于等于R即可,如果小于等于R就把他俩所在的集合合并,最后求集合个数即可。用并查集维护。实现时注意,每两个点判断是否符合条件时需要验证x坐标和y坐标,具体实现可以把一个点拆分成两个点,碰到第一个点就把它加入平衡树中,以y坐标作为关键字,碰到第二个点就删除之即可。当然平衡树自然可以使用树状数组+二分+离散化代替。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<map> using namespace std; #define maxn 300005 #define connect(x,y) father[getfather((x))] = getfather((y)) int ans,n,r,father[maxn]; vector<pair<pair<int,int>,pair<int,int> > > point; map<int,int> past; map<int,int>::iterator t1,t2; int getfather(int x){ if(father[x] == x) return x; father[x] = getfather(father[x]); return father[x]; } int main(){ freopen("bomb.in","r",stdin); freopen("bomb.out","w",stdout); scanf("%d%d",&n,&r); memset(father,-1,sizeof(father)); for(int i = 0;i<n;i++) father[i] = i; for(int i = 0;i<n;i++){ int x0,y0; scanf("%d%d",&x0,&y0); point.push_back(make_pair(make_pair(x0+y0,1),make_pair(i,x0-y0))); point.push_back(make_pair(make_pair(x0+y0+r+1,-1),make_pair(i,x0-y0)));//for erasing points first } sort(point.begin(),point.end()); for(int i = 0;i<point.size();i++){ int x = point[i].first.first,p = point[i].first.second,w = point[i].second.first,y = point[i].second.second; t1 = past.find(y); if(p == -1){ if((*t1).second == w) past.erase(t1); } else{ if(t1 != past.end()){connect(w,(*t1).second);past.erase(t1);} else{ t1 = past.upper_bound(y),t2 = past.lower_bound(y); if(t1 != past.end() && ((*t1).first)-y <= r) connect(w,(*t1).second); if(t2 != past.begin() && y - (*(--t2)).first <= r) connect(w,(*t2).second); } past.insert(make_pair(y,w)); } } for(int i = 0;i<n;i++) ans += getfather(i) == i; printf("%d\n",ans); return 0; }