UPD：好像有两道题的代码逃跑了？= =就先不找了，反正都是水题。
精简题解系列第四弹。（其实也不是那么精简啊= =）
[JSOI2008]最大数maxnumber
单点修改，区间最大值查询，裸线段树
/**************************************************************
Problem: 1012
User: wsc500
Language: C++
Result: Accepted
Time:944 ms
Memory:5368 kb
****************************************************************/ #include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm> using namespace std;
#define MAXN (262144+2)
#define Q (262143)
#define bigger(a,b) ((a)>(b)?(a):(b)) /*Gloable*/
int m,d;
int T[MAXN*];
/*Function*/
void insert(int p,int val){
T[p+Q]=val;
int i=p+Q;
while (i!=){
T[i/]=bigger(T[i/*],T[i/*+]);
i/=;
}
}
int query(int L,int R,int a,int b,int p){
//printf("%d %d %d %d %d\n",L,R,a,b,p);
if (R>b) R=b;
if (L<a) L=a;
if (L==a&&R==b) return T[p]; int mid=(a+b)/;
int ans1,ans2;
ans1=ans2=; if (L<=mid) ans1=query(L,R,a,mid,p*);
if (R>mid) ans2=query(L,R,mid+,b,p*+); return bigger(ans1,ans2);
}
int main()
{
memset(T,,sizeof(T));
int x,t=,n=;
char cmd[];
scanf("%d%d",&m,&d);
for (int i=;i<=m;i++){
//printf("hehe\n");
scanf("%s%d",cmd,&x);
if (cmd[]=='A'){
insert(n,(x+t)%d);
n++;
}
if (cmd[]=='Q'){
//printf("hehe");
t=query(n-x,n-,,Q+,);
printf("%d\n",t);
}
} return ;
}
[JSOI2008]球形空间产生器sphere
果然前两道都是水题T_T。题中给出了公式，那么列出n+1个式子果断考虑解方程。首先开方可以忽略，对于平方的问题，相邻两个等式相减，利用平方差可以吧未知数的平方约掉。那么正好n+1个式子得出n和一次方程，高斯消元即可。很少写高斯消元啊，1A真开心= =
/**************************************************************
Problem: 1013
User: wsc500
Language: C++
Result: Accepted
Time:0 ms
Memory:1276 kb
****************************************************************/ #include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std;
#define MAXN (10+5)
#define bigger(a,b) ((a)>(b)?(a):(b)) /*Gloable*/
double data[MAXN+][MAXN];
double M[MAXN][MAXN];
int n;
/*Function*/
void readData(){
scanf("%d",&n);
for (int i=;i<=n+;i++){
for (int j=;j<=n;j++){
scanf("%lf",&data[i][j]);
}
}
}
void setGuass(){
for (int i=;i<=n+;i++){
for (int j=;j<=n;j++){
M[i-][j]=2.0*(data[i][j]-data[i-][j]);
M[i-][n+]+=(data[i][j]+data[i-][j])*(data[i][j]-data[i-][j]);
}
}
}
void sloveGuass(){
for (int i=;i<=n;i++){
int r=i;
for (int j=i+;j<=n;j++){
if (fabs(M[j][i])>fabs(M[r][i])) r=j;
}
for (int j=;j<=n+;j++) swap(M[i][j],M[r][j]); for (int j=i+;j<=n;j++){
double f=M[j][i]/M[i][i];
for (int k=i;k<=n+;k++){
M[j][k]-=M[i][k]*f;
}
}
} for (int i=n;i>=;i--){
for (int j=i+;j<=n;j++){
M[i][n+]-=M[i][j]*M[j][n+];
}
M[i][n+]/=M[i][i];
}
}
void printAns(){
for (int i=;i<=n-;i++){
printf("%.3lf ",M[i][n+]);
}
printf("%.3lf\n",M[n][n+]);
}
int main()
{
memset(M,,sizeof(M));
readData();
setGuass();
sloveGuass();
printAns();
return ;
}
[JSOI2008]星球大战starwar
进击的水题= =离线倒过来搞就是裸的并差集了
[JSOI2008]最小生成树计数
终于不算水题了。。可以发现一个性质：最小生成树中某种边权的边的数量是固定的，有注意到相同边权的边不超过10条，所以先求最小生成树然后2^10枚举子集，判断即可。
[JSOI2009]游戏Game
在图上的博弈问题。突然就想起了NOI那道[兔兔和蛋蛋的游戏]，然后就明白了。都是一个模型，本质上是二分图增广路的性质。
简单来说，如果先手放在一个【一定在最大匹配内】的点上，那么必输。为什么呢？因为这是后手可以移动到其对应的匹配点上。如果先手继续移动到匹配点上，那么后手可以沿着最大匹配的交错轨移动，所以只要先手移动，后手一定能移动，而且最后是先手不能移动（因为如果先手又能移动了，那么就得到了一条增广路，那么互换匹配边和非匹配变后最大匹配+1，因为最大匹配已经求出来了，所以显然不存在增广路，所以最后先手不能继续移动到匹配点）。如果先手移动到了未匹配点上，那么后手可以继续移动到一个匹配点，就和刚才一样了。所以可知，先手放在一个【一定在最大匹配内】的点上，那么必输。
同理，如果先手放在一个【不一定在最大匹配内】的点上，那么就必胜了。因为这时后手不得不移动到非匹配点，如同上面的过程，就是先手占了优势，所以先手必胜。
那么问题就简单了。把网格黑白染色，求最大匹配。
如何判断一个点是否一定在最大匹配上呢？对于X部，从S开始沿残量网络DFS，不能走到的点就一定在最大匹配上。同理对于Y部把原图反向，从T开始DFS。
这又是为什么呢？(= =) 还是考虑增广路，DFS的过程实际上得到了一条交错轨，那么互换匹配边与非匹配边后匹配点一定不变，因为变了就出现了增广路。所以这些点在任意一种最大匹配中都是匹配点。
那么就完事了。
做这道题的时候不幸发现 我的好友【智商】已经下线，所以代码就不贴了。。。反正是写了200+行的巨挫代码。
[JSOI2009]Count
果然我还是就会做水题T_T。每种颜色开一个BIT，单点修改区间和查询。
/**************************************************************
Problem: 1452
User: wsc500
Language: C++
Result: Accepted
Time:4516 ms
Memory:42940 kb
****************************************************************/ #include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector> using namespace std;
#define MAXN (300+10)
#define MAXC (100+10)
#define lowbit(i) (i&(-i)) /*Gloable*/
int data[MAXN][MAXN];
int m,n;
/*Function*/
struct BIT{
int t[MAXN][MAXN];
void add(int x,int y,int val){
for (int i=x;i<=n;i+=lowbit(i))
for (int j=y;j<=m;j+=lowbit(j))
t[i][j]+=val;
}
int _query(int x,int y){
int rtn=;
for (int i=x;i>=;i-=lowbit(i)){
for (int j=y;j>=;j-=lowbit(j)){
rtn+=t[i][j];
}
}
return rtn;
}
int query(int xa,int ya,int xb,int yb){
return _query(xb,yb)-_query(xb,ya-)-_query(xa-,yb)+_query(xa-,ya-);
}
}B[MAXC]; void readData(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
scanf("%d",&data[i][j]);
}
}
}
void init(){
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
B[data[i][j]].add(i,j,);
}
}
}
void work(){
int q,cmd,a,b,c,d,e;
scanf("%d",&q);
for (int i=;i<=q;i++){
scanf("%d",&cmd);
if (cmd==){
scanf("%d%d%d",&a,&b,&c);
B[data[a][b]].add(a,b,-);
B[c].add(a,b,);
data[a][b]=c;
}
if (cmd==){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
printf("%d\n",B[e].query(a,c,b,d));
}
}
}
int main()
{
readData();
init();
work();
return ;
}
[JSOI2009]去括号
这是以前做的那道。好像直接乱搞就可以了？忘了。代码就不贴了
[JSOI2010]Group 部落划分 Group
可以二分答案，然后统计块数。也可以直接给所有点对按距离从小到大排序，逐个合并直到块数<k。
/**************************************************************
Problem: 1821
User: wsc500
Language: C++
Result: Accepted
Time:488 ms
Memory:17236 kb
****************************************************************/ #include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath> using namespace std;
#define MAXN (1000+10)
#define minner(a,b) ((a)<(b)?(a):(b)) /*Gloable*/
struct pos{
double x,y;
pos(double x=0.0,double y=0.0):x(x),y(y) {}
};
typedef struct pos pos;
pos data[MAXN];
int n,k,L;
pair<double,pair<int,int> > lst[MAXN*MAXN];
int fa[MAXN],blocks;
/*Function*/
void init(){
for (int i=;i<=MAXN;i++) fa[i]=i;
blocks=n;
}
int find(int x){
int a=x,temp;
while (x!=fa[x]) x=fa[x];
while (a!=fa[a]) temp=fa[a] , fa[a]=x , a=temp;
return x;
}
void join(int x,int y){
int fx=find(x),fy=find(y);
if (fx!=fy) fa[fx]=fy , blocks--;
}
inline double getDis(pos a,pos b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void readData(){
double a,b;
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++){
scanf("%lf%lf",&a,&b);
data[i]=pos(a,b);
}
}
void work(){
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (i!=j) lst[L++]=make_pair(getDis(data[i],data[j]),make_pair(i,j));
sort(lst,lst+L);
if (blocks<k) {printf("%.2lf\n",lst[].first);return;}
for (int i=;i<L;i++){
join(lst[i].second.first,lst[i].second.second);
if (blocks<k) {printf("%.2lf\n",lst[i+].first);break;}
}
}
int main()
{
readData();
init();
work();
return ;
}
[Jsoi2010]连通数
直接缩环这很明显了吧。刚开始以为按拓扑序像DP一样更新就行了，但发现有重复计算。那么就对每个点染色或者求最短路，反正是DAG怎么搞都是O(n)。然后对于每个可达的块把点数乘起来最后累加就行了。总复杂度n^2。网上有人说n^2超时了，那肯定是写搓了。还有那个n^3压位是怎么来的？说是O(n)我还信。。。反正这种方法好写好调。1A。
UPD：我又想了一下，好像DP是可以的。。压一下状态，记录都是从那几个点过来的，然后按拓扑序转移状态就行了。。这是不是网上说的那种方法？但绝对不是n^3。
/**************************************************************
Problem: 2208
User: wsc500
Language: C++
Result: Accepted
Time:8072 ms
Memory:63836 kb
****************************************************************/ #include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector> using namespace std;
#define MAXN (2000+10)
#define MAXM (2000*2000+10)
#define minner(a,b) ((a)<(b)?(a):(b)) /*Debug*/ #define debug /*Gloable*/
struct Graph{
int head[MAXN],next[MAXM],e[MAXM],countside;
void buildside(int a,int b){
e[countside]=b;
next[countside]=head[a];
head[a]=countside++;
}
Graph(){
memset(head,,sizeof(head));
memset(next,,sizeof(next));
memset(e,,sizeof(e));
countside=;
}
}G1,G2;
int n;
int dfs_clock,SCC_id;// for tarjan()
int id[MAXN],lowlink[MAXN],mark[MAXN];// for tarjan()
bool inStack[MAXN];// for tarjan()
stack<int> S; // for tarjan()
bool v[MAXN];// for color()
int ct[MAXN],ans[MAXN];// for ans;
/*Function*/
void tarjan_dfs(int p){
id[p]=lowlink[p]=dfs_clock++;
S.push(p);
inStack[p]=true;
for (int i=G1.head[p];i>;i=G1.next[i]){
if (id[G1.e[i]]==-){
tarjan_dfs(G1.e[i]);
lowlink[p]=minner(lowlink[p],lowlink[G1.e[i]]);
}else if(inStack[G1.e[i]]){
lowlink[p]=minner(lowlink[p],id[G1.e[i]]);
}
}
if (lowlink[p]==id[p]){
while (){
int now=S.top();S.pop();
inStack[now]=false;
mark[now]=SCC_id;
if (now==p) break;
}
SCC_id++;
}
}
void tarjan(){
for (int i=;i<=n;i++) id[i]=-;
memset(inStack,false,sizeof(inStack));
dfs_clock=;
SCC_id=;
for (int i=;i<=n;i++) if (id[i]==-) tarjan_dfs(i); for (int i=;i<=n;i++) ct[mark[i]]++;
}
void readData(){
char str[MAXN];
scanf("%d",&n);
for (int i=;i<=n;i++){
scanf("%s",str);
for (int j=;j<n;j++) if (str[j]=='') G1.buildside(i,j+);
}
}
void rebuild(){
for (int i=;i<=n;i++){
for (int j=G1.head[i];j>;j=G1.next[j])
if (mark[i]!=mark[G1.e[j]]) {
G2.buildside(mark[i],mark[G1.e[j]]);
//cout<<mark[i]<<" "<<mark[G1.e[j]]<<endl;
}
}
n=SCC_id-;
}
void color(int p){
queue<int> q;
q.push(p);
//v[p]=true;
while (!q.empty()){
int now=q.front();q.pop();
for (int i=G2.head[now];i>;i=G2.next[i])
if (!v[G2.e[i]]) v[G2.e[i]]=true , q.push(G2.e[i]);
}
}
void work(){
for (int i=;i<=n;i++){
memset(v,false,sizeof(v));
color(i);
for (int j=;j<=n;j++) if (v[j])
ans[j]+=ct[i]*ct[j];
}
}
void printAns(){
int result=;
for (int i=;i<=n;i++) result+=ans[i] , result+=ct[i]*(ct[i]);
printf("%d\n",result);
}
int main()
{
readData();
tarjan();
rebuild();
work();
printAns();
return ;
}
[Jsoi2009]瓶子和燃料
首先那个倒水问题的最小答案是瓶子容量们的最大公约数。原理等同于辗转相减（还是叫更相减损？）。那么问题就转化成了给出n个数，选出k个是他们的GCD最大。进一步转化就是求一个最大的数使他是至少k个数的约数。那么就把每个数因式分解（注意不是质因数分解），然后找到出现次数>=k且大小最大的因数就行了，因为肯定有解，所以直接按出现次数和数字大小排一下序就行了。
/**************************************************************
Problem: 2257
User: wsc500
Language: C++
Result: Accepted
Time:2244 ms
Memory:7132 kb
****************************************************************/ #include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std;
#define MAXN (1000001+10)
#define MAXF (500000) /*Gloable*/
int lst[MAXF],v[MAXN],s;
int n,k;
/*Function*/
void readData(){
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++) scanf("%d",&v[i]);
}
void getPrimeFact(int x){
int i;
for (i=;i*i<x;i++){
if (x%i==) lst[s++]=i , lst[s++]=x/i;
//while (x%i!=0) x/=i;
}
if (i*i==x) if (x%i==) lst[s++]=i;
}
void work(){
for (int i=;i<=n;i++)
getPrimeFact(v[i]);
sort(lst,lst+s);
int st=,mx=;
lst[s]=-;
for (int i=;i<s;i++){
if (lst[i+]!=lst[i]){
if (i+-st>=k&&lst[i]>lst[mx]) mx=i;
st=i+;
}
}
printf("%d\n",lst[mx]);
}
int main()
{
readData();
work();
return ;
}