牛客IOI周赛
周赛22
A-战争尾声：暴力O(200*200*n)
思路：
给定的国家的范围再（1，1）到（200，200），那么依次计算这里面的每个点到各个国家的距离是否相等，找到相等的那个点即可，又因为如果有多个距离相等的点优先取x最小的，再x相等就去y最小的，那我们x从1开始遍历，y从1开始遍历，最先满足条件的就是答案。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
struct node{
int x,y;
}node[1005];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> node[i].x >> node[i].y;
}
int i,j,cnt = 0;
for(i = 1; i <= 200; i++){
for(j = 1; j <= 200; j++){
cnt = 0;
int len = (i-node[1].x)*(i-node[1].x)+(j-node[1].y)*(j-node[1].y);
for(int k = 1; k <= n; k++){
if(len == (i-node[k].x)*(i-node[k].x)+(j-node[k].y)*(j-node[k].y))
cnt++;
}
if(cnt == n) break;
}
if(cnt == n) break;
}
if(i > 200) cout << "War is cruel." << endl;
else cout << i << " " << j << endl;
return 0;
} B-签订协议：思维O(n)
大意：
协议书要从战斗力高的国家先签，然后依次传向战斗力低的国家签，如果传到了最后传给了位置1的人算一个回合，问所有国家都签完最少要几个回合。
思路：
每个国家有两个属性，战斗力和位置，按位置给所有国家排序，然后判断相邻位置国家的战斗力，如果战斗力小的国家的位置在战斗力高的国家前面，那么战斗力高的
国家签完后会重新回到位置1战斗力低的那个国家才能签。依次判断下去就是答案。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
struct Node{
int x,y;
bool operator < (const Node &a)const{
return x > a.x;
}
}node[900005];
int a[900005];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&node[i].x),node[i].y = i;
sort(node+1,node+n+1);
int cnt = 1;
for(int i = 1; i < n; i++){
if(node[i].y > node[i+1].y) cnt++;
}
printf("%d",cnt);
return 0;
} C-照看小猫：思维+排列组合+预处理O(n)
大意：
n个小猫有互不相同的名字，并且每个小猫都有自己名字长度的限制，即这个小猫的名字不能超过限制的超度，但可以小于这个长度。先给出n个小猫名字的限制长度，问给这n个小猫取名字有多少中不同的方式。
思路：
优先处理名字限制短的，为了保证名字不重复，后面小猫的名字取法种类数为在不加限制的情况下的种类是减去前面有多少个小猫，依次相乘取模。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int a[10005];
ll sum[15];
int main()
{
int n;
sum[1] = 26;
for(int i = 2; i <= 10; i++) sum[i] = sum[i-1]*26;
for(int i = 2; i <= 10; i++) sum[i] = sum[i-1] + sum[i];
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1,a+n+1);
ll ans = 1;
int flag = 0;
for(int i = 0; i < n; i++){
ll t = sum[a[i+1]] - i;
if(t <= 0) {
flag = 1;
cout << "-1";
break;
}
//t *= 77797;
ans = (ans*t)%77797;
}
if(!flag) cout << ans%77797;
return 0;
} D-路线规划：最小生成树(模板)
思路：
走完n个点并且回来，要求花费最少的时间是多少，想想最小生成树的定义，其实就是最小生成树*2.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
struct Edge{
int u,v;
ll w;
bool operator < (const Edge &x) const{
return x.w > w;
}
}edge[2000005];
int f[200005];
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 0; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++){
scanf("%d%d%lld",&edge[i].u,&edge[i].v,&edge[i].w);
}
sort(edge+1,edge+m+1);
ll ans = 0;
int cnt = 0;
for(int i = 1; i <= m; i++){
int x = find(edge[i].u);
int y = find(edge[i].v);
if(x != y){
cnt++;
f[x] = f[y];
ans += edge[i].w;
if(cnt == n-1) break;
}
}
printf("%lld\n",ans*2);
return 0;
} 周赛19
C-小y的旅行：并查集
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
struct edge{
int x,y;
}edge[2000005];
int f[1000005];
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
void merge(int x,int y)
{
x = find(x);
y = find(y);
if(x != y) f[x] = f[y];
}
int main()
{
int n,m,k,cnt;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++){
cin >> edge[i].x >> edge[i].y;
if(edge[i].x > k && edge[i].y > k){
merge(edge[i].x,edge[i].y);
}
}
int ans = 0;
for(int i = 1; i <= m; i++){
if(edge[i].x <= k || edge[i].y <= k){
int x = find(edge[i].x);
int y = find(edge[i].y);
if(x == y){
ans++;
}
f[x] = f[y];
}
}
cout << ans << endl;
return 0;
} 周赛17
B-莫的难题：进制转化
大意：
给五个数字5，2，1，3，9 每个数字可以取无限次，取好的数字可以组合在一起，问第C(n,m)%1e9+7是哪个数字。
思路：
先从小到大摆出一些数来看看，1，2，3，5，9，11，12，13，15，19，21，22，23，25，29，31，32，33，35，39......
我们把这5个数字看成0，1，2，3，4
那么上面摆出的数可以看成是 0，1，2，3，4，10，11，12，13，14，20，21，22，23，24，
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int f[105][105];
void init()
{
f[0][0] = 1;
for(int i = 1; i <= 100; i++){
for(int j = 0; j <= i; j++){
if(j == 0) {
f[i][j] = 1;
continue;
}
if(i == j){
f[i][j] = 1;
continue;
}
f[i][j] = (f[i-1][j]+f[i-1][j-1])%mod;
}
}
// for(int i = 0; i <= 7; i++){
// for(int j = 0; j <= i; j++){
// cout << f[i][j] << " ";
// }
// cout << endl;
// }
}
char s[10] = {'1','2','3','5','9'};
int main()
{
int t,n,m;
init();
cin >> t;
while(t--){
cin >> n >> m;
int k = f[n][m];
// cout << k << endl;
string str = "";
while(k){
k--;
str += s[k%5];
k /= 5;
}
reverse(str.begin(),str.end());
cout << str << endl;
}
return 0;
} C-不平衡数组：动态规划O(n)
思路：
对于每个数可以选择加一或者不加，两种选择，要想到用dp来做。
找状态：两者选择，两种状态，dp[i][1]第i个数加一的最小代价，dp[i][0]第i个数不加的情况
状态转移：加1和不加时不能和前面一个数起冲突，有下面四种情况
if(a[i-1] != a[i]) dp[i][0] = min(dp[i][0],dp[i-1][0]);//不加 第i个数不能和第i-1个数相等 if(a[i-1] != a[i]-1) dp[i][0] = min(dp[i][0],dp[i-1][1]);//不加 第i个数不能和第i-1个数加一后相等 if(a[i-1] != a[i]+1) dp[i][1] = min(dp[i][1],dp[i-1][0]+b[i]);//加 加完后不能和第i个数相等 if(a[i-1]+1 != a[i]+1) dp[i][1] = min(dp[i][1],dp[i-1][1]+b[i]);//加 加完后不能和第i个数加完后的数相等
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
ll dp[200005][2];
int n,m;
int a[200005],b[200005];
ll ans = 0;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i] >> b[i];
}
for(int i = 1; i<= n; i++){
dp[i][0] = ds;
dp[i][1] = ds;
}
dp[1][0] = 0;
dp[1][1] = b[1];
for(int i = 2; i <= n; i++){
if(a[i-1] != a[i]) dp[i][0] = min(dp[i][0],dp[i-1][0]);
if(a[i-1] != a[i]-1) dp[i][0] = min(dp[i][0],dp[i-1][1]);
if(a[i-1] != a[i]+1) dp[i][1] = min(dp[i][1],dp[i-1][0]+b[i]);
if(a[i-1]+1 != a[i]+1) dp[i][1] = min(dp[i][1],dp[i-1][1]+b[i]);
}
cout << min(dp[n][0],dp[n][1]) << endl;
return 0;
} D-数列统计：排列组合(动态规划推出公式)
大意：
求以x结尾的长度为l的序列有多少个。
思路：
考虑用dp来做。
状态：dp[i][j] 表示长度为i以j的数结尾的序列有多少个。
状态转移：
，怎么来的，如果固定第i为是j，那第i-1为只能是1...j，求和后就是dp[i][j]的答案
初值：dp[i][1] = 1,dp[1][i] = i
多列出几个值可以发现答案就是
上面是长度，下面是长度加结尾值-1
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 911451407;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
using namespace std;
int qpow(int a,int b)
{
ll res = 1;
while(b){
if(b&1) res = res*a%mod;
b >>= 1;
a = 1ll*a*a%mod;
}
return res;
}
int f[10000005];
void init()
{
f[0] = 1;
for(int i = 1; i <= 10000005; i++){
f[i] = 1ll*f[i-1]*1ll*i%mod;
}
}
int up,don;
int main()
{
int t,l,x,ans;
init();
scanf("%d",&t);
while(t--){
scanf("%d%d",&l,&x);
up = f[l+x-2];
don = 1ll*f[l-1]*1ll*f[x-1]%mod;
don = qpow(don,mod-2);
ans = 1ll*up*1ll*don%mod;
printf("%d\n",ans);
}
return 0;
} 
