Eddy Walker
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Eddy likes to walk around. Especially, he likes to walk in a loop called "Infinite loop". But, actually, it's just a loop with finite length(Anyway, the name doesn't matter). Eddy can walk in a fixed length. He finds that it takes him N steps to walk through the loop a cycle. Then, he puts N marks on the "Infinite loop" labeled with 0, 1, \ldots, N-10,1,…,N−1, where i and i+1 are a step away each other, so as 0 and N-1. After that, Eddy stands on the mark labeled 0 and start walking around. For each step, Eddy will independently uniformly randomly choose to move forward or backward. If currently Eddy is on the mark labeled i, he will on the mark labeled i+1 if move forward or i-1 if move backward. If Eddy is on the mark labeled N-1 and moves forward, he will stand on the mark labeled 0. If Eddy is on the mark labeled 0 and moves backward, he will stand on the mark labeled N-1.
Although, Eddy likes to walk around. He will get bored after he reaches each mark at least once. After that, Eddy will pick up all the marks, go back to work and stop walking around.
You, somehow, notice the weird convention Eddy is doing. And, you record T scenarios that Eddy walks around. For i-th scenario, you record two numbers N_iNi, M_iMi, where N_iNi tells that in the i-th scenario, Eddy can walk through the loop a cycle in exactly N_iNi steps(Yes! Eddy can walk in different fixed length for different day.). While M_iMi tells that you found that in the i-th scenario, after Eddy stands on the mark labeled M_iMi, he reached all the marks.
However, when you review your records, you are not sure whether the data is correct or even possible. Thus, you want to know the probability that those scenarios will happen. \textbf{Precisely, you are going to compute the probability that first i scenarios will happen sequentially for each i.}Precisely, you are going to compute the probability that first i scenarios will happen sequentially for each i.
输入描述:
The first line of input contains an integers T.
Following T lines each contains two space-separated integers N_iNi and M_iMi.
1 \leq T \leq 10211≤T≤1021
0 \leq M_i < N_i \leq 10^90≤Mi<Ni≤109
输出描述:
Output T lines each contains an integer representing the probability that first i scenarios will happen sequentially.
you should output the number module 10^9+7(1000000007)109+7(1000000007).
Suppose the probability is \frac{P}{Q}QP, the desired output will be P \times Q^{-1} \mod 10^9+7P×Q−1mod109+7
示例1
输入
3 1 0 2 1 3 0
输出
1 1 0
暴力乱搞，最后再求个前缀和即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const ll mod=(ll)1e9+7;
ll n,ans=1;
ll qpow(ll base,ll n){
ll res=1;
while(n){
if(n&1) res=res*base%mod;
base=base*base%mod;
n>>=1;
}
return res%mod;
}
ll inv(ll b){return qpow(b,mod-2)%mod;}
void solve(){
scanf("%lld",&n);
rep(i,1,n){
ll a,b;scanf("%lld%lld",&a,&b);
ans=ans*(a==1?1:(b==0?0:(inv(a-1)%mod)))%mod;
printf("%lld\n",ans);
}
}
int main(){
solve();
}
Partition problem
时间限制：C/C++ 4秒，其他语言8秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Given 2N people, you need to assign each of them into either red team or white team such that each team consists of exactly N people and the total competitive value is maximized.
Total competitive value is the summation of competitive value of each pair of people in different team.
The equivalent equation is ∑i=12N∑j=i+12N(vij if i-th person is not in the same team as j-th person else 0)\sum_{i=1}^{2N} \sum_{j=i+1}^{2N} (v_{ij} \text{ if i-th person is not in the same team as j-th person else } 0 )∑i=12N∑j=i+12N(vij if i-th person is not in the same team as j-th person else 0)
输入描述:
The first line of input contains an integers N.
Following 2N lines each contains 2N space-separated integers vijv_{ij}vij is the j-th value of the i-th line which indicates the competitive value of person i and person j.
* 1≤N≤141 \leq N \leq 141≤N≤14
* 0≤vij≤1090 \leq v_{ij} \leq 10^{9}0≤vij≤109
* vij=vjiv_{ij} = v_{ji}vij=vji
输出描述:
Output one line containing an integer representing the maximum possible total competitive value.
示例1
输入
1 0 3 3 0
输出
3
将所有人分成两队，暴力dfs卡常就过了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e4+100;
int n;
int v[30][30];
int top,sta[100],mark[110];
ll sum[110],ma=-1,res;
void dfs(int re,int pos){
if(!re){
ll tmp=res;
for(int i=1;i<=top;++i)
for(int j=i+1;j<=top;++j) tmp-=v[sta[i]][sta[j]]<<1;
ma=max(ma,tmp);
return;
}
for(int i=pos;n-i>=re;++i){
res+=sum[i];
sta[++top]=i;
dfs(re-1,i+1);
res-=sum[i];
top--;
}
return;
}
int main(){
while(scanf("%d",&n)!=EOF){
n<<=1; ma=-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&v[i][j]);
sum[i]+=v[i][j];
}
}
dfs(n>>1,1);
printf("%lld\n",ma);
}
return 0;
Second Large Rectangle
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Given a N×MN \times MN×M binary matrix. Please output the size of second large rectangle containing all "1"\texttt{"1"}"1".
Containing all "1"\texttt{"1"}"1" means that the entries of the rectangle are all "1"\texttt{"1"}"1".
A rectangle can be defined as four integers x1,y1,x2,y2x_1, y_1, x_2, y_2x1,y1,x2,y2 where 1≤x1≤x2≤N1 \leq x_1 \leq x_2 \leq N1≤x1≤x2≤N and 1≤y1≤y2≤M1 \leq y_1 \leq y_2 \leq M1≤y1≤y2≤M. Then, the rectangle is composed of all the cell (x, y) where x1≤x≤x2x_1 \leq x \leq x_2x1≤x≤x2 and y1≤y≤y2y_1 \leq y \leq y2y1≤y≤y2. If all of the cell in the rectangle is "1"\texttt{"1"}"1", this is a valid rectangle.
Please find out the size of the second largest rectangle, two rectangles are different if exists a cell belonged to one of them but not belonged to the other.
输入描述:
The first line of input contains two space-separated integers N and M.
Following N lines each contains M characters cijc_{ij}cij.
1≤N,M≤10001 \leq N, M \leq 10001≤N,M≤1000
N×M≥2N \times M \geq 2N×M≥2
cij∈"01"c_{ij} \in \texttt{"01"}cij∈"01"
输出描述:
Output one line containing an integer representing the answer. If there are less than 2 rectangles containning all "1"\texttt{"1"}"1", output "0"\texttt{"0"}"0".
示例1
输入
1 2 01
输出
0
示例2
输入
1 3 101
输出
1
简单DP
#include<iostream>
#include<cstdio>
using namespace std;
int z,x,n,m,w,h,a[1010][1010],t[1010],tt[1010];
char c;
int main()
{
scanf("%d%d",&z,&x);w=0;h=0;
for (int i=1;i<=z;i++)
{
m=0;
getchar();
for (int j=1;j<=x;j++)
{
n=getchar()-'0';
if (n) a[i][j]=a[i-1][j]+1;
if (n) { t[++m]=j;tt[m]=a[i][j];}
while (m>1&&tt[m]<=tt[m-1]) { tt[m-1]=tt[m];m--;}
if (!n) m=0;
for (int k=1;k<=m;k++)
if (w<tt[k]*(j-t[k]+1))
{
h=w;w=tt[k]*(j-t[k]+1);
} else
if (h<tt[k]*(j-t[k]+1)) h=tt[k]*(j-t[k]+1);
}
}
printf("%d",h);
return 0;
}
