题目1 : 序列
描述
给定两个正整数 n, P，求满足以下两个条件的长度为 n 的序列 ai 个数：
1. 1 ≤ ai ≤ P
2. 不存在 1 ≤ l ≤ r ≤ n，满足al + al+1 + ... + ar 是 P 的倍数
由于方案数可能很大，你只需要输出方案数对 109+7 取模的值
输入
第一行两个正整数 n,P
1 ≤ n, P ≤ 104
输出
输出方案数对 109+7 取模的值
样例解释
满足条件的序列有两个：{1,1} 和 {2,2}
样例输入
2 3
样例输出
2
#include <iostream>
#define ll long long using namespace std; const ll MOD = ; int main()
{
ll n, p;
while(cin>>n>>p){
ll ans = ;
p--;
while(n--){
ans *= p;
ans %= MOD;
p--;
}
cout<<ans<<endl;
} return ;
}
题目2 : 彩球
描述
有一家商店，一共有 n × k 个彩球。球一共有 n 种颜色，每种颜色的球都是有恰好 k 个，现在你要从这 n×k 个球中选 n 个球，要求他们的颜色互不相同，求有几种选择的方案，由于方案数可能很大，你只需要输出方案数对 P 取模后的值。
输入
第一行三个正整数 n, k, P
对于50%的数据，有1 ≤ n, k, P ≤ 109
对于100%的数据，有1 ≤ n, k, P ≤ 1018
输出
输出方案数对 P 取模后的值
- 样例输入
-
2 2 100000
- 样例输出
-
4
def quick_pow(a, n, mod):
ans = 1
while(n!=0):
if(n%2==1):
ans = ans*a%mod
a = a*a%mod
n = n // 2
return ans if __name__ == '__main__':
n, k, mod = raw_input().strip().split()
n = long(n)
k = long(k)
mod = long(mod)
print quick_pow(k, n, mod)
题目3 : 最优子段
描述
给定一个长度为 n 的序列 ai 和两个整数 A, B，要求你找一对数l, r，要求1 ≤ l ≤ r 且A×(ai+ai+1+...+ar)+B 最大
输入
第一行三个整数 n, A, B
第二行 n 个整数，第 i 个整数表示 ai
1 ≤ n ≤ 106
-106 ≤ A, B, ai ≤ 106
输出
输出最大的A×(ai+ai+1+...+ar)+B
样例解释
选择 (1,1) 或者 (4,4) 都可以
- 样例输入
-
4 2 3
0 -2 -2 0 - 样例输出
-
3
#include <iostream>
#define ll long long using namespace std; const int N = ; ll arr[N]; ll dp(ll n){
ll ans = ;
ll sum = ;
for(int i = ; i <n; i++){
sum += arr[i];
ans = max(ans, sum);
if(sum < )sum = ;
}
return ans;
} int main()
{
ll n, A, B;
while(cin>>n>>A>>B){
for(int i = ; i < n; i++){
cin>>arr[i];
if(A<)arr[i] *= -;
}
if(A<)cout<<-A*dp(n)+B<<endl;
else cout<<A*dp(n)+B<<endl;
} return ;
}
题目4 : 公路收费
描述
A 国有 n 个城市，第 i 个城市有 ai 个会议代表，这 n 个城市通过 n-$ 条双向的高速公路连接，保证每两个城市都可以通过高速公路互相到达，每个人通过一条高速公路都要付相应的费用。
现在 A 国的总统想挑选一个城市作为会议中心，要求全国所有会议代表都到这个城市来，为了方便大家出行，A 国的总统可以让不超过 k 条高速公路的收费变为 0 。
现在你要安排挑选的城市和免费的高速公路，最小化的所有会议代表的路费总和。
输入
第一行两个整数 n, k
第二行 n 个非负整数，第 i 个表示ai
接下来 n-1 行，每行三个整数 u, v, w，描述一条收费为 w 的高速公路 (u, v)
1 ≤ n ≤ 103
0 ≤ k ≤ n-1
1 ≤ w, ai≤ 105
输出
输出最小的路费总和
样例解释
让 (2,3) 免费，然后选 2 作为会议城市
- 样例输入
-
3 1
1 2 3
1 2 1
2 3 2 - 样例输出
-
1
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> #define ll long long using namespace std; const int N = ;
const ll INF = 0x3f3f3f3f3f3f3f3f; ll arr[N], sum[N]; struct Edge{
int to, w, next;
}edges[*N];
int head[N], tot; void init(){
memset(head, -, sizeof(head));
tot = ;
} void add_edge(int u, int v, int w){
edges[tot].to = v;
edges[tot].w = w;
edges[tot].next = head[u];
head[u] = tot++;
} vector<ll> vec;
int n, k; void dfs(int u, int fa){
sum[u] = arr[u];
for(int i = head[u]; i != -; i = edges[i].next){
int v = edges[i].to;
int w = edges[i].w;
if(v != fa){
dfs(v, u);
sum[u] += sum[v];
vec.push_back(sum[v]*w);
}
}
} ll work(int s){
vec.clear(); dfs(s, );
sort(vec.begin(), vec.end());
ll ans = ;
for(int i = ; i < n-k-; i++)
ans += vec[i];
return ans;
} int main()
{
while(cin>>n>>k){
for(int i = ; i <= n; i++)
cin>>arr[i];
int u, v, w;
init();
for(int i = ; i < n-; i++){
cin>>u>>v>>w;
add_edge(u, v, w);
add_edge(v, u, w);
}
ll ans = INF;
for(int i = ; i <= n; i++){
ans = min(ans, work(i));
}
cout<<ans<<endl;
}
return ;
}