2021.11.02 eleveni的水省选题的记录
因为eleveni比较菜，所以eleveni决定从绿题开始水
——实际上菜菜的eleveni连绿题都不一定能水过/忍不住哭了
[P2217 HAOI2007]分割矩阵 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题看着像dfs，实际上就是dfs+dp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=20;
int n,m,k,sum[N][N];
double average,f[N][N][N][N][N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline double query(int x,int y,int u,int v){
return sum[u][v]-sum[x-1][v]-sum[u][y-1]+sum[x-1][y-1];
}
inline double pf(double x){
return x*x;
}
inline double dfs(int x,int y,int u,int v,int step){
if(f[x][y][u][v][step])return f[x][y][u][v][step];
if(step==1)return pf(query(x,y,u,v)-average);
f[x][y][u][v][step]=0x3f3f3f3f;
for(int i=x;i<u;i++)for(int j=1;j<step;j++)
f[x][y][u][v][step]=min(f[x][y][u][v][step],dfs(x,y,i,v,j)+dfs(i+1,y,u,v,step-j));
for(int i=y;i<v;i++)for(int j=1;j<step;j++)
f[x][y][u][v][step]=min(f[x][y][u][v][step],dfs(x,y,u,i,j)+dfs(x,i+1,u,v,step-j));
return f[x][y][u][v][step];
}
int main(){
n=read();m=read();k=read();
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
int x=read();
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
}
average=(double)sum[n][m]/(double)k;
double ans=dfs(1,1,n,m,k);
ans/=(double)k;ans=sqrt(ans);
printf("%.2lf",ans);
return 0;
}
[P1984 SDOI2008] 烧水问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
建议出题人好好学学语文！！！
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
double ans,jz;
int n;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
n=read();
jz=420000/(double)n;
for(int i=1;i<=n;i++){
ans+=jz;
jz*=1.0-0.5/(double)i;
}
printf("%.2lf",ans);
return 0;
}
[P1627 CQOI2009]中位数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
有折半搜索那味儿了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N=1e5+10;
int n,m,pos,a[N],ans,now;
map<int,int>mapi;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++){
a[i]=read();
if(a[i]==m)pos=i;
if(pos>0){
if(a[i]>m)++now;
else if(a[i]<m)--now;
++mapi[now];
}
}
now=0;
for(int i=pos;i>=1;i--){
if(a[i]>m)++now;
else if(a[i]<m)--now;
ans+=mapi[0-now];
}
cout<<ans;
}
[P2252 SHOI2002]取石子游戏|【模板】威佐夫博弈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
威佐夫博弈：
（自己只推出了（1，2）先手必败，只要能一步转移到（1，2），先手必胜，结果……这玩意儿还有公式，shitf！）
题解 P2252 【取石子游戏】 - 蒟蒻wyx 的博客 - 洛谷博客 (luogu.com.cn)
威佐夫博弈 - chen_zhe 的博客 - 洛谷博客 (luogu.com.cn)
\[我们局势为为(a[k],b[k](a[k] \leq b[k],k \in [0,n]))
\\我们定义一个奇异局势为可以让先手A必输的局势。
\\例如在上面这个题中，
\\可以找到类似于(1,2),(3,5),(4,7)等奇异局势。
\\
由此可得：
\\a[0]=b[0]=0,\\a[k]是未在前面出现过的最小自然数,而b[k]=a[k]+k。
\]
\[如果我给你一个局势(a,b)，
\\如何判断这是不是一个奇异局势呢？
\\有一个很好用的公式如下：
\\
\begin{cases}a[k]=\lfloor \dfrac{k \times (1+\sqrt{5})}{2} \rfloor \\b[k]=a[k]+k\end{cases}
\\其中 k \in N
\\由此我们可以得知：
\\若两堆物品个数分别为x,y(x<y)，
\\则k=y-x，再判断x是否等于\lfloor (y-x)\times \dfrac{1+\sqrt{5})}{2} \rfloor即可得知是否是奇异局势。
\]
——来自chen_zhe博客
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
const double lorry=(sqrt(5.0)+1.0)/2.0;
int main(){
cin>>n>>m;
if(n<m)swap(n,m);
int k=n-m;
if(m==(int)((double)k*lorry))cout<<"0";
else cout<<"1";
return 0;
}
[P2296 NOIP2014 提高组] 寻找道路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
感觉之前做过这题，可水了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4+10;
int n,m,start,endi,cnt,head[N],vis[N],dis[N];
struct node{
int to,next;
}a[N*20];
struct nodei{
int pos,dis;
bool operator <(const nodei &b)const{
return dis>b.dis;
}
};
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void dijkstra(int s){
priority_queue<nodei>q;
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[s]=0;
q.push({s,0});
while(!q.empty()){
nodei tmp=q.top();q.pop();
int x=tmp.pos;
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(dis[v]>dis[x]+1){
dis[v]=dis[x]+1;
if(!vis[v])q.push({v,dis[v]});
}
}
}
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int u,v;
u=read();v=read();
add(v,u);
}
endi=read();start=read();
dijkstra(start);
//for(int i=1;i<=n;i++)cout<<dis[i]<<" ";cout<<endl;
queue<int>q;
for(int i=1;i<=n;i++)if(dis[i]==0x3f3f3f3f)q.push(i);//,cout<<i<<endl;
memset(vis,0,sizeof(vis));
while(!q.empty()){
int x=q.front();q.pop();
vis[x]=1;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
vis[v]=1;
}
}
//for(int i=1;i<=n;i++)cout<<vis[i]<<" ";cout<<endl;
dijkstra(start);
if(dis[endi]==0x3f3f3f3f)cout<<"-1";
else cout<<dis[endi];
return 0;
}
[P1128 HNOI2001] 求正整数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
根据唯一分解定理：
\[n=p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*\cdots*p_k^{a_k}
\]
可以知道n的因数个数为
\[（a_1+1)*(a_2+1)*(a_3+1)*\cdots*(a_k+1)
\]
10分代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e4+10;
typedef long long ll;
int n,top,topi,tot,isprime[N],prime[N];
ll ans;
struct node{
int num,tot;
bool operator <(const node &b)const{
return num>b.num;
}
}a[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline ll ksm(int x,int y){
ll fin=1;
while(y){
if(y&1)fin*=x;
x*=x;
y>>=1;
}
return fin;
}
int main(){
n=read();
int ni=n;
for(int i=n-1;i>1;i--){
if(ni==1)break;
if(ni%i)continue;
++top;
a[top].num=i-1;
//a[top].tot=-1;
while(ni%i==0)++a[top].tot,ni/=i;
tot+=a[top].tot;
}
if(ni>1)++top,a[top].num=ni-1,a[top].tot=1;
sort(a+1,a+top+1);
//for(int i=1;i<=top;i++)cout<<a[i].num<<" "<<a[i].tot<<endl;
for(int i=2;i<=n*n;i++)isprime[i]=1;
for(int i=2;i<=n;i++){
if(isprime[i]){
prime[++topi]=i;
if(topi==tot)break;
for(int j=i*i;j<=n;j+=i)isprime[j]=0;
}
}
//for(int i=1;i<=tot;i++)cout<<prime[i]<<" ";cout<<endl;
ans=1;
topi=0;
for(int i=1;i<=top;i++){
for(int j=1;j<=a[i].tot;j++){
int x=prime[++topi];
ans=ans*ksm(x,a[i].num);
}
}
cout<<ans;
return 0;
}
满分代码：
PS：需要用log优化、高精
题解上有，但是我不想写，先咕着。——2021.11.02
![2022-04-01：有n个人，m个任务，任务之间有依赖记录在int[][] depends里。 比如: depends[i] = [a, b]，表示a任务依赖b任务的完成， 其中 0 ＜= a ＜](https://www.kunjuke.com/file/css/thumb/10.jpg/280-180.jpg)
