A - Uint47 calculator FZU - 2294
水题，用unsigned long long,自带自动溢出，然后就可以随便写了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
ull mod=1;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
string s;
map<string,ull> mp;
int main() {
char op[100];
string tx,ty;
ull x,y;
for(int i=1;i<48;i++){
mod*=2;
}
while(~scanf("%s",op)) {
if(op[0]=='d'&&op[1]=='e') { //def
cin>>s>>x;
mp[s]=x;
cout<<s<<" = "<<x<<'\n';
} else if(op[0]=='s') { //sub
cin>>tx>>ty;
x=mp[tx];
y=mp[ty];
mp[tx]=x=(x-y+mod)%mod;
cout<<tx<<" = "<<x<<'\n';
} else if(op[0]=='a') {
cin>>tx>>ty;
x=mp[tx];
y=mp[ty];
mp[tx]=x=(x+y)%mod;
cout<<tx<<" = "<<x<<'\n';
} else if(op[0]=='m'&&op[1]=='u') {
cin>>tx>>ty;
x=mp[tx];
y=mp[ty];
mp[tx]=x=(x*y)%mod;
cout<<tx<<" = "<<x<<'\n';
} else if(op[0]=='d') {
cin>>tx>>ty;
x=mp[tx];
y=mp[ty];
mp[tx]=x=(x/y)%mod;
cout<<tx<<" = "<<x<<'\n';
} else {
cin>>tx>>ty;
x=mp[tx];
y=mp[ty];
mp[tx]=x=x%y;
cout<<tx<<" = "<<x<<'\n';
}
}
return 0;
} B - Human life FZU - 2295
最大权闭合子图，k只有5暴力枚举所有状态。然后就是一个裸题了。
答案 是最大正权值-去最大流。如果有人想了解为啥，自行百度吧。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=1e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int v[maxn];
int pre[maxn][maxn];
int u[maxn];
int n,m,K;
int a[2][5];
int ku[maxn];
vector<int> tv[maxn];
struct edge {
int to,cap,rev;
};
vector <edge> G[maxn];
int level[maxn];
int iter[maxn];
void init(int _n) {
for(int i=0; i<=_n; i++) {
G[i].clear();
tv[i].clear();
}
mem(pre,0);
mem(u,0);
}
void init(){
for(int i=0;i<=n+m+1;i++)G[i].clear();
}
void bfs(int s) {
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty()) {
int v= que.front();
que.pop();
for(int i=0; i<G[v].size(); i++) {
edge & e=G[v][i];
if(e.cap>0&&level[e.to]<0) {
level[e.to]=level[v] + 1;
que.push(e.to);
}
}
}
}
void add(int from,int to,int cap) {
edge eg;
eg.to=to;
eg.cap=cap;
eg.rev=G[to].size();
G[from].push_back(eg);
eg.to=from;
eg.cap=0;
eg.rev=G[from].size()-1;
G[to].push_back(eg);
}
int dfs(int v,int t,int f) {
if(v == t)return f;
for(int &i = iter[v]; i < G[v].size(); i++) {
edge &e=G[v][i];
if(e.cap>0 && level[v]<level[e.to]) {
int d=dfs(e.to,t,min(f,e.cap));
if(d>0) {
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int maxflow(int s,int t) {
int flow=0;
for(;;) {
bfs(s);
if(level[t]<0)return flow;
memset(iter,0,sizeof(iter));
int f;
while((f = dfs(s,t,INF))>0) {
flow +=f;
}
}
}
void dfs(int r) {
u[r]=1;
for(int i=1; i<=n; i++) {
if(pre[r][i]) {
if(u[i]==0) {
dfs(i);
}
for(int j=1; j<=n; j++) {
pre[r][j]|=pre[i][j];
}
}
}
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%d%d%d",&n,&m,&K);
init(n+m+1);
for(int i=1; i<=n; i++) {
scanf("%d",&v[i]);
int k;
scanf("%d",&k);
if(k==0)u[i]=1;
for(int j=0; j<k; j++) {
int x;
scanf("%d",&x);
pre[i][x]=1;
}
}
for(int i=1; i<=n; i++) {
if(u[i]==0) {
dfs(i);
}
}
for(int i=n+1; i<=n+m; i++) {
scanf("%d",&v[i]);
int k;
bool tu[maxn]= {0};
scanf("%d",&k);
for(int j=0; j<k; j++) {
int x;
scanf("%d",&x);
if(tu[x])continue;
tu[x]=1;
for(int l=1; l<=n; l++) {
tu[l]|=pre[x][l];
}
}
for(int j=1; j<=n; j++) {
if(tu[j]) {
tv[i].push_back(j);
}
}
}
for(int i=0; i<K; i++) {
scanf("%d%d",&a[0][i],&a[1][i]);
}
int mx=0;
for(int i=0; i<1<<K; i++) {
mem(ku,0);
init();
for(int j=0; j<K; j++) {
ku[a[(i>>j)&1][j]+n]=1;
// debug(a[(i>>j)&1][j]+n);
}
int sum=0;
for(int i=n+1; i<=n+m; i++) {
if(ku[i]==1)continue;
// debug(i);
add(0,i,v[i]);
for(int j=0; j<tv[i].size(); j++) {
add(i,tv[i][j],inf);
}
sum+=v[i];
}
for(int i=1; i<=n; i++)add(i,n+m+1,v[i]);
mx=max(sum-maxflow(0,n+m+1),mx);
}
printf("%d\n",mx);
}
return 0;
} D - Number theory FZU - 2297
一开始还以为是大数，java 了一发，大数了一发，全都TLE，正解就是一个线段树。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=1e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int c[maxn][maxn];
int q[maxn][maxn];
int b2[maxn];
long long pow(long long x,long long n,long long mod=1e9+7) {
long long res=1;
while(n>0) {
if(n&1)res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res%mod;
}
int main() {
c[1][1]=1;
c[1][0]=1;
for(int i=1; i<1e3+1; i++) {
c[i+1][0]=1;
// printf("%d ",c[i+1][0]);
for(int j=1; j<=i+1; j++) {
c[i+1][j]=(c[i][j-1]+c[i][j])%mod;
// printf("%d ",c[i+1][j]);
}
}
for(int i=1; i<1e3+1; i++) {
for(int j=0; j<=i; j++) {
q[i][j+1]=(q[i][j]+c[i][j])%mod;
}
}
b2[0]=1;
for(int i=1; i<1e3+1; i++) {
b2[i]=(b2[i-1]*2)%mod;
}
int t;
scanf("%d",&t);
while(t--) {
int n,m;
scanf("%d%d",&n,&m);
if(m>n) {
puts("0");
} else {
cout<<(q[n][n+1]-q[n][m]+mod)%mod*pow(b2[n],mod-2,mod)%mod<<endl;
}
}
return 0;
} E - Traffic jamFZU - 2298
最短路，处理下到某个点的情况，如果是红灯，时间变为到绿灯开始。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int a[maxn];
int cost[maxn];
int n,m;
struct edge {
int to,c,next;
} eg[maxn*2];
int head[maxn],tot,vis[maxn];
void init() {
mem(head,-1);
tot=0;
}
void add(int u,int v,int c) {
eg[tot].to=v;
eg[tot].c=c;
eg[tot].next=head[u];
head[u]=tot++;
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
init();
for(int i=0; i<m; i++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
int st,en;
scanf("%d%d",&st,&en);
queue<int> q;
q.push(st);
mem(cost,inf);
mem(vis,0);
cost[st]=0;
while(q.size()) {
int v=q.front();
q.pop();
vis[v]=0;
for(int i=head[v]; i!=-1; i=eg[i].next) {
int d=cost[v]+eg[i].c,to=eg[i].to;
if(to!=en&&(d/a[to])&1)d=(d/a[to]+1)*a[to];
if(d<cost[to]) {
cost[to]=d;
if(vis[to]==0) {
vis[to]=1;
q.push(to);
}
}
}
}
printf("%d\n",cost[en]);
}
return 0;
} G - IoU FZU - 2300
签到题
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
ull mod=1;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
string s;
map<string,ull> mp;
int T;
struct node {
ll x,y,w,h;
}a[3];
int main() {
scanf("%d", &T);
while (T --) {
scanf("%lld %lld %lld %lld", &a[0].x,&a[0].y,&a[0].w,&a[0].h);
scanf("%lld %lld %lld %lld", &a[1].x,&a[1].y,&a[1].w,&a[1].h);
ll wi = (min(a[0].x+a[0].w, a[1].x+a[1].w)-max(a[0].x, a[1].x));
ll hi = (min(a[0].y+a[0].h, a[1].y+a[1].h)-max(a[0].y, a[1].y));
ll un;
if(wi > 0 && hi > 0) un = wi*hi;
else un = 0;
//debug(un);
ll sum = a[0].w*a[0].h+a[1].w*a[1].h-un;
//debug(sum);
printf("%.2f\n", 1.0*un/sum);
}
return 0;
}
/*
6
1 1 1 1
1 1 2 2
1 1 2 1
1 1 1 2
1 1 2 2
2 0 1 1
0 3 3 3
2 2 2 1
0 3 3 3
2 4 5 5
1 1 1 1
-100 -100 1 1
*/ H - Chosen by god FZU - 2301
题意：n点伤害随机分配，求分配到敌人身上大于等于m，的期望，就是求C(M,N)+...+C(M,N);
题解：打个组合数的表，然后前缀处理一下。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=1e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int c[maxn][maxn];
int q[maxn][maxn];
int b2[maxn];
long long pow(long long x,long long n,long long mod=1e9+7) {
long long res=1;
while(n>0) {
if(n&1)res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res%mod;
}
int main() {
c[1][1]=1;
c[1][0]=1;
for(int i=1; i<1e3+1; i++) {
c[i+1][0]=1;
// printf("%d ",c[i+1][0]);
for(int j=1; j<=i+1; j++) {
c[i+1][j]=(c[i][j-1]+c[i][j])%mod;
// printf("%d ",c[i+1][j]);
}
}
for(int i=1; i<1e3+1; i++) {
for(int j=0; j<=i; j++) {
q[i][j+1]=(q[i][j]+c[i][j])%mod;
}
}
b2[0]=1;
for(int i=1; i<1e3+1; i++) {
b2[i]=(b2[i-1]*2)%mod;
}
int t;
scanf("%d",&t);
while(t--) {
int n,m;
scanf("%d%d",&n,&m);
if(m>n) {
puts("0");
} else {
cout<<(q[n][n+1]-q[n][m]+mod)%mod*pow(b2[n],mod-2,mod)%mod<<endl;
}
}
return 0;
} J - Mind control FZU - 2303
题意：n个人，m个蛋糕，你把蛋糕给一个人，他后面的人也会被选上，例如选1 ，2 3 4 5 ....等都会被选上，选 3 4 5 ...都会被选上，求选上人数的期望。
题解：给蛋糕的总肯能是C（M,N），选的人最高为1 的选择种数是，C（M-1,N-1），选一个蛋糕给1，然后其他蛋糕给他后面的人，以此类推，最高为2 选择种数是 ,C(M-1,N-2)，最高为3 可能是 C（m-1,N-3）;
然后权值乘以概率就是期望 ，N*C(M-1,N-1)+(N-1)*C(M-1,N-2)+....+M*C(M-1,M-1)/C(M,N)；
看到权值是 N,N-1肯定要化进组合数 ，大答案*m/m, 就可以化成M*C(M,N)+M*(M,N-1)+.....+M*C(M,M)/C(M,N)；
在化简 M*C(M+1,N+1)/C(M,N)最后化为M*(N+1)/(M+1)；
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
long long pow(long long x,long long n,long long mod=1e9+7) {
long long res=1;
while(n>0) {
if(n&1)res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res%mod;
}
void read(ll &sum) {
sum=0;
int flag=0;
char ch=getchar();
while(!(ch>='0'&&ch<='9')) {
if (ch == '-') {
flag = 1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=getchar();
if(flag)sum*=-1;
}
int main() {
ll t;
read(t);
while(t--) {
ll n,m;
read(n);
read(m);
cout<<m*(n+1)%mod*pow(m+1,mod-2,mod)%mod<<"\n";
}
return 0;
}
京公网安备 11010502036488号