C:
题意:
有 n 个整数 ai, 数列 a 有两个神奇的性质. 1. 所有的整数都在 [l,r] 范围内. 2. 这 n 个数的和能被 3 整除. 现在给出 l 和 r, 和个数 n, 问你有多少种方法构造出数列 a, 方案数 mod1e9+7.
题解:
一个数被 3 除只有三种可能. 1. 整除, 2. 余 1,2. 余 2.
然后我们再想这个问题,[l,r]区间内, 能被 3 整除的数有多少? a0=r/3-l/3. 余 1/2 的数有多少? a1/2=((r-l+1)-a0)/2.(这里具体余 1 和余 2 不重要, 想想为什么)
我们设 f[i][j]为前 i 个数, 和除 3 余 j 的方案数. 怎么转移呢.
- f[i][0]=f[i-1][1]*a2+f[i-1][2]*a1+f[i-1][0]*a0.
- f[i][1]=f[i-1][0]*a1+f[i-1][1]*a0+f[i-1][2]*a2.
- f[i][2]=f[i-1][0]*a2+f[i-1][1]*a1+f[i-1][2]*a0.
- #include<stdio.h>
- #include<iostream>
- using namespace std;
- long long dp[200005][3];
- const long long mod=1000000007;
- int main(){
- int n,l,r;
- cin>>n>>l>>r;
- long long a0,a1,a2;
- long long sum=r-l+1;
- a0=r/3-(l-1)/3;
- sum-=a0;
- a1=sum/2;
- a2=sum-a1 ;
- dp[1][0]=a0;
- dp[1][1]=a1;
- dp[1][2]=a2;
- for(int i=2;i<=n;i++)
- {
- dp[i][0]=(dp[i-1][1]*a2+dp[i-1][0]*a0+dp[i-1][2]*a1)%mod;
- dp[i][1]=(dp[i-1][1]*a0+dp[i-1][0]*a1+dp[i-1][2]*a2)%mod;
- dp[i][2]=(dp[i-1][1]*a1+dp[i-1][0]*a2+dp[i-1][2]*a0)%mod;
- }
- printf("%I64d\n",dp[n][0]);
- }
- View Code
D. 题意
kilani 正在和朋友们玩一个游戏, 这个游戏在一个 n*m 的网格上, 每个格子要么是空白, 要么是已经被占领, 每个玩家有一个或者多个城堡. 每个玩家轮流进行游戏. 对于玩家 i, 他可以从一个已有的城堡向一个空白的格子扩建一个城堡, 如果这个空白的格子和它的曼哈顿距离不超过 s[i].
求游戏结束后每个玩家占领的格子数量.
题解:
一个多源 bfs. 具体可以看代码
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <iostream>
- #include <queue>
- #define pir pair<int,int>
- #define mkp make_pair
- using namespace std;
- const int maxn=1000+10;
- const int dx[]={0,0,1,-1};
- const int dy[]={1,-1,0,0};
- int n,m,p;
- int a[10],ans[10];
- char G[maxn][maxn];
- int vis[maxn][maxn];
- struct Node{
- int x,y,p;
- };
- int main(){
- scanf("%d%d%d",&n,&m,&p);
- for(int i=1;i<=p;i++){
- scanf("%d",&a[i]);
- }
- queue<pir>q;
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- scanf("%c",&G[i][j]);
- }
- }
- for(int k=1;k<=p;k++){
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- // scanf("%c",&G[i][j]);
- if(G[i][j]!='.'&&G[i][j]!='#'&&G[i][j]-'0'==k){
- vis[i][j]=k;
- q.push(mkp(i,j));
- }
- }
- }
- }
- while(!q.empty()){
- pir u=q.front();q.pop();
- int x=u.first,y=u.second;
- int num=vis[x][y];
- queue<Node>q2;
- q2.push({x,y,a[num]});
- while(!q.empty()){
- pir u1=q.front();
- if(vis[u1.first][u1.second]==num){
- q.pop();
- q2.push({u1.first,u1.second,a[num]});
- }else{
- break;
- }
- }
- while(!q2.empty()){
- Node u1=q2.front();q2.pop();
- if(u1.p<=0)continue;
- for(int k=0;k<4;k++){
- int nx=u1.x+dx[k];
- int ny=u1.y+dy[k];
- if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&G[nx][ny]=='.'&&vis[nx][ny]==0){
- vis[nx][ny]=num;
- q2.push({nx,ny,u1.p-1});
- q.push(mkp(nx,ny));
- }
- }
- }
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- if(vis[i][j]){
- ans[vis[i][j]]++;
- //printf("%d",vis[i][j]);
- }
- }
- //printf("\n");
- }
- for(int i=1;i<=p;i++){
- printf("%d",ans[i]);
- }
- return 0;
- }
- View Code
- E. Helping Hiasat
题意:
Hiasat 有一个社交账号, 当他的朋友们每次来看他社交首页的时候, 如果他首页的名字是这个朋友的名字, 他朋友就会很开心. 给出一个序列代表可以修改名字的时间和朋友们来访问的顺序, 问如何修改才能让开心的朋友们最多.
题解:
显然在两次修改之间的所有访问, 只能满足一次. 那么其实很显然, 将这些点之间连边, 然后求图的最大独立集. 然后最大独立集怎么求? 求补图中的最大团. 最大团怎么求? 套板子啊!!
- include <bits/stdc++.h>
- using namespace std;
- const int maxn = 55;
- bool mp[maxn][maxn];
- int num[maxn], group[maxn], now[maxn];
- int n, m, ans;
- bool dfs(int u, int cnt)
- {
- int i, j;
- for(i = u+1; i <= n; ++i)
- {
- if(num[i]+cnt <= ans) return false; //???3
- if(mp[u][i])
- {
- for(j = 0; j <cnt; ++j)
- if(!mp[i][now[j]]) break;
- if(j == cnt) //???
- {
- now[cnt] = i;
- if(dfs(i, cnt+1)) return true;
- }
- }
- }
- if(cnt> ans)
- {
- for(i = 0; i <cnt; ++i)
- group[i] = now[i];
- ans = cnt;
- return true;
- }
- return false;
- }
- int MaximumClique()
- {
- ans = -1;
- for(int i = n; i>= 1; --i)
- {
- now[0] = i;
- dfs(i, 1);
- num[i] = ans;
- }
- return ans;
- }
- map<string,int>Name;
- int name_num;
- int N,M;
- int G[maxn][maxn];
- int main()
- {
- scanf("%d%d",&N,&M);
- vector<int>per;
- set<int>S;
- for(int i=1;i<=N;i++){
- int type;
- scanf("%d",&type);
- if(type==1){
- per.clear();
- S.clear();
- }else{
- string name;
- cin>>name;
- if(!Name.count(name)){
- Name[name]=++name_num;
- }
- if(!S.count(Name[name])){
- S.insert(Name[name]);
- for(int i=0;i<per.size();i++){
- int u=per[i];
- G[u][Name[name]]=1;
- G[Name[name]][u]=1;
- }
- per.push_back(Name[name]);
- }
- }
- }
- n=name_num;
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- mp[i][j]=!G[i][j];
- }
- }
- printf("%d\n",MaximumClique());
- // while(cin>> n && n)
- // {
- // for(int i = 1; i <= n; ++i)
- // for(int j = 1; j <= n; ++j)
- // {
- // int x; cin>> x;
- // mp[i][j] = x;
- // }
- // cout << MaximumClique() << endl;
- // }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2956107.html