A：水题，模拟。
#include <bits/stdc++.h>
using namespace std;
int a[100][100];
int n;
bool check(int r, int c){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(a[r][i]+a[j][c]==a[r][c]) return 1;
}
}
return 0;
}
int main()
{
bool flag=1;
scanf("%d",&n);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&a[i][j]);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(a[i][j]==1) continue;
if(check(i,j)==0) flag=0;
}
}
if(flag) puts("Yes");
else puts("No");
}B，枚举每一个纵坐标的可能点，根据直线表达式算出对应的x，只要统计出当前(x,y)和坐标轴的矩形的答案，去和全局维护的最优答案比较即可。我们发现计算x,y下方所有的点的横纵坐标之和可以利用两次等差数列来算，这个就很简单了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL m, b, x, y;
int main()
{
scanf("%lld%lld",&m,&b);
LL ans1=0,ans=0;
for(int y=0; y<=b; y++)
{
x = (b-y)*m;
ans1=0;
ans1+=(x+1)*(y+1)*y/2;
ans1+=x*(y+1+(y+1)*x)/2;
ans=max(ans,ans1);
}
printf("%lld\n", ans);
return 0;
}C,题意就是有两个操作，add就是往栈里push一个数，remove就是移除栈顶元素。现在要求数字按照1-n的顺序移除。问至少需要改动多少次，改动的意思就是把当前栈里面的元素排序。 解法：直接用vector模拟这个过程,add就直接add,remove的时候要是不满足就直接清空vector。
#include <bits/stdc++.h>
using namespace std;
vector <int> v;
char s[10];
int n, x;
int main()
{
scanf("%d", &n);
int cnt = 1, ans = 0;
for(int i=1; i<=n*2; i++){
scanf("%s", s);
if(s[0]=='a'){
scanf("%d", &x);
v.push_back(x);
}
else{
if(v.empty());
else if(v.back()==cnt) v.pop_back();
else{
ans++,v.clear();
}
cnt++;
}
}
printf("%d\n", ans);
return 0;
}D,有个n*m的矩形上面有k盏灯，没盏灯占了一个格子。只能走有灯的格子，但是当在一个原始就有灯的地方可以花费1使得一行或者一列变亮，现在要求你从左上角(1,1)走到右下角(n,m)，求最小花费。
题解：首先把题目上的k个点当成图中的点，由于站在一个初始亮的点可以点亮一行一列，所以我们可以在这个点上，点亮相邻的一行或者一列。所以想到一个图论比较常见的套路，引入行列作为图中的点，然后以k个点，外加k个行形成的点，k个列形成的点来建图。从1个点到相邻行列的花费是1，反向花费是0。还有图本身就有的边，以及为了便于处理在(n,m)没有灯的情况下增加1个k+1这个点表示(n,m)，然后跑一遍最短路算法。
这里写代码片#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000;
const int inf = 0x3f3f3f3f;
struct edge{
int to, w, next;
edge(){}
edge(int to, int w, int next):to(to),w(w),next(next){}
}E[maxn*2];
int head[maxn], edgecnt, dis[maxn];
void init(){
memset(head,-1,sizeof(head));
edgecnt=0;
}
void add(int u, int v, int w){
E[edgecnt].to=v,E[edgecnt].w=w,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
pair<int, int> p[maxn];
map <pair<int, int>, int> mp;
bool vis[maxn];
int n, m, k;
void Dij(int s){
priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > >q;
for(int i = 0; i < maxn; i++) dis[i] = inf;
memset(vis, 0, sizeof(vis));
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
pair<int,int> p = q.top(); q.pop();
int u = p.second;
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u]; ~i; i=E[i].next){
int v = E[i].to, w = E[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
q.push(make_pair(dis[v], v));
}
}
}
}
int main()
{
init();
scanf("%d %d %d", &n,&m,&k);
int bas = 1e4+7;
for(int i=1; i<=k; i++){
int r, c;
scanf("%d %d", &r,&c);
add(i,r+bas,1);
add(i,c+2*bas,1);
add(i,r+bas+1,1);
add(i,c+2*bas+1,1);
add(i,r+bas-1,1);
add(i,c+2*bas-1,1);
add(r+bas,i,0);
add(c+2*bas,i,0);
add(r+bas+1,i,0);
add(c+2*bas+1,i,0);
add(r+bas-1,i,0);
add(c+2*bas-1,i,0);
p[i] = {r, c};
mp[make_pair(r,c)] = i;
}
for(int i=1; i<=k; i++){
for(int j=0; j<4; j++){
int x = p[i].first+dir[j][0];
int y = p[i].second+dir[j][1];
if(mp.find(make_pair(x,y))!=mp.end()){
add(i,mp[make_pair(x,y)],0);
}
}
}
if(mp.find(make_pair(n,m))==mp.end()){
add(n+bas,k+1,0);
add(m+2*bas,k+1,0);
}
Dij(mp[make_pair(1,1)]);
int ans;
if(mp.find(make_pair(n,m))==mp.end()){
ans = dis[k+1];
}
else{
ans = dis[mp[make_pair(n,m)]];
}
if(ans == inf) ans = -1;
printf("%d\n", ans);
return 0;
}E,
我们现在位于（0,0）处，目标是走到（K，0）处。
每一次我们都可以从（x，y）走到（x+1，y-1）或者（x+1，y）或者（x+1，y+1）三个位子之一。
现在一共有N段线段，每条线段都是平行于X轴的。
我们如果此时x是在这段线段之内的话，我们此时走到的点（x，y）需要满足0<=y<=Ci.
现在保证一段线段的终点，一定是下一段线段的起点。
问我们从起点走到终点的行走方案数。
解法：比赛的时候看到很多人在群里说这个题就是分段的矩阵快速幂，很简单。只能感叹这个世界太强，我快要go die了。首先考虑一下线段只有一条并且k很小，那么可以想到一个朴素的递推。dp[i][j]表示走到(i,j)的方案数。那么有
初始化dp[0][0] = 1
但是这里k很大，那么我们利用矩阵快速幂对每一段的状态转移过程快速幂优化即可。注意到ci<=15。我们可以这样构造这个转移矩阵
这个过程维护到达上一次线段终点的可行方案数，然后继续转移下一条线段，知道最后为止。
参考博客：http://blog.csdn.net/mengxiang000000/article/details/73740695
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
///分段矩阵快速幂
const LL mod = 1e9+7;
struct Matrix{
LL maze[17][17];
void init(){
memset(maze,0,sizeof(maze));
}
};
Matrix A,B,pre;
Matrix mul(Matrix a, Matrix b, LL len){
Matrix res;
res.init();
for(int i=0; i<=len; i++)
for(int j=0; j<=len; j++)
for(int k=0; k<=len; k++)
res.maze[i][j] = (res.maze[i][j]+(a.maze[i][k]%mod*b.maze[k][j]%mod)%mod)%mod;
return res;
}
Matrix ksm(Matrix a, LL n, LL len){
Matrix res;
res.init();
for(int i=0; i<=len; i++){
res.maze[i][i]=1;
}
while(n){
if(n&1) res = mul(res, a, len);
a = mul(a, a, len);
n >>= 1;
}
return res;
}
int main()
{
LL n, en;
scanf("%lld%lld", &n, &en);
pre.init();
A.init();
for(int i=0; i<16; i++){
for(int j=i-1; j<i+2&&j<16; j++){
if(j>=0&&j<=15){
A.maze[i][j]=1;
}
}
}
bool ok = 0;
pre.maze[0][0] = 1;
for(int i=1; i<=n; i++){
LL L, R, y;
scanf("%lld %lld %lld", &L, &R, &y);
if(R > en) R = en, ok = 1;
B = ksm(A, R-L, y);
for(LL j=y+1; j<=15; j++) pre.maze[j][0]=0;
B = mul(B, pre, y);
for(int j=0; j<=y; j++){
pre.maze[j][0] = B.maze[j][0];
}
if(ok) break;
}
printf("%lld\n", B.maze[0][0]);
return 0;
}
京公网安备 11010502036488号