B. The writing on the wall
我们可以一列一列的看，如果该列没有黑点的话，那么ans+=(1+n)*n/2，如果有黑点的话，可以用set维护被黑点分开的区间，那么再计算这个区间长度就能得到这个区间的贡献了。
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int, int> P;
const int N = (int)1e5 + 500, M = 105;
int n,m,k,x,y;
bool vis[N];
vector<int> pt[M];
set<P> S;ll get(int t){return 1LL * t * (t + 1) / 2;
}int main(){int T, kase = 0;scanf("%d", &T);while(T--){for(int i = 0; i < M; i++) pt[i].clear();scanf("%d%d%d", &n, &m, &k);for(int i = 0; i < k; i++){scanf("%d%d", &x, &y);x--, y--;pt[y].push_back(x);}ll ans = 0;for(int i = 0; i < m; i++){S.clear();fill(vis, vis+n, false);S.insert({
0, n-1});ll cur = get(n);for(int j = i; j < m; j++){for(int pti : pt[j]){if(!vis[pti]){vis[pti] = true;auto it = S.upper_bound({pti, 1000000});it--;int l = it->first, r = it->second;S.erase(it);cur -= get(r - l + 1);if(pti - 1 >= l){cur += get(pti - l);S.insert({l, pti - 1});}if(pti + 1 <= r){cur += get(r - pti);S.insert({pti + 1, r});}}}//cout << i << ", " << j << ": " << cur << endl;ans += cur;}}cout << "Case #" << ++kase << ": " << ans << endl;}
}详解可戳这里
C. GDY暴力模拟即可。。
#include <bits/stdc++.h>
using namespace std;const int N = 205, M = 20050;
typedef pair<int, int> P;multiset<int> S[15];
int n,m,a;
multiset<int> cd[N];
queue<int> card;bool get_a_card(int i){if(card.empty()) return false;int c = card.front(); card.pop();cd[i].insert(c);S[c].insert(i);return true;
}int nxtcard(int c){assert(c != 2);return c != 13 ? c + 1 : 1;
}void spare(int p, int c){//cout << "player " << p + 1 << " sparing card " << c << endl;cd[p].erase(cd[p].find(c));S[c].erase(S[c].find(p));
}int nxt_card_play(int loc, int card){auto it1 = S[card].upper_bound(loc);if(it1 != S[card].end()) return *it1;auto it2 = S[card].lower_bound(0);if(it2 != S[card].end() && *it2 != loc) return *it2;return -1;
}int comp(int nxt, int loc){if(nxt < loc) return nxt + n;return nxt;
}int nxtplayer(int loc, int cur_c){if(cur_c == 2) return -1;int nxt1 = nxt_card_play(loc, nxtcard(cur_c));int nxt2 = nxt_card_play(loc, 2);if(nxt1 == -1 && nxt2 == -1) return -1;if(nxt1 == -1 || nxt2 == -1) return nxt1 == -1 ? nxt2 : nxt1;return comp(nxt1, loc) <= comp(nxt2, loc) ? nxt1 : nxt2;
}int get_smallest(int loc){auto it = cd[loc].lower_bound(3);if(it != cd[loc].end()) return *it;it = cd[loc].lower_bound(1);return *it;
}int main(){int T, kase = 0;cin >> T;while(T--){cin >> n >> m;for(int i = 0; i < N; i++) cd[i].clear();for(int i = 0; i < 15; i++) S[i].clear();while(!card.empty()) card.pop();for(int i = 0; i < m; i++){cin >> a;card.push(a);}for(int i = 0; i < n; i++){for(int j = 0; j < 5 && !card.empty(); j++){int c = card.front(); card.pop();cd[i].insert(c);S[c].insert(i);}}
// for(int i = 0; i < n; i++){
// cout << "player " << i << ": ";
// for(int c : cd[i]){
// cout << c << " ";
// }
// cout << endl;
// }
// cout << "ok1" << endl;int now_p = 0;int nxt = get_smallest(now_p);while(true){spare(now_p, nxt);if(cd[now_p].size() == 0){break;}int nxt_p = nxtplayer(now_p, nxt);//cout << "next player is " << nxt_p << endl;if(nxt_p == -1){if(get_a_card(now_p)){for(int j = (now_p+1)%n; j != now_p && get_a_card(j); j = (j + 1) % n);}nxt = get_smallest(now_p);}else{if(cd[nxt_p].find(nxtcard(nxt)) != cd[nxt_p].end()){nxt = nxtcard(nxt);}else nxt = 2;now_p = nxt_p;}}cout << "Case #" << ++kase << ":\n";for(int i = 0; i < n; i++){if(cd[i].size() == 0) cout << "Winner" << endl;else{int sum = 0;for(int c : cd[i]) sum += c;cout << sum << endl;}}}
}E. AC Challenge
n只有20，那么可以以二进制表示当前完成的任务的状态，然后记忆化搜索即可。
#include<bits/stdc++.h>
using namespace std;const int maxn=20;
long long dp[(1<<maxn)+10];
struct node
{int a,b;int have;node(int a,int b,int have):a(a),b(b),have(have){}node(){}
}P[maxn];
int n;
long long dfs(int t,int state)
{if(dp[state]!=-1)return dp[state];if(state==((1<<n)-1))return 0;long long res=0;for(int i=0;i<n;i++)if(((state>>i)&1)==0){if((P[i].have&state)==P[i].have){res=max(res,dfs(t+1,state+(1<<i))+P[i].a*t+P[i].b);}}return dp[state]=res;
}int main()
{memset(dp,-1,sizeof(dp));scanf("%d",&n);int a,b;for(int i=0;i<n;i++){scanf("%d %d",&a,&b);int s;scanf("%d",&s);int res=0;int tmp;while(s--){scanf("%d",&tmp);tmp--;res+=(1<<tmp);}P[i]=node(a,b,res);}dfs(1,0);printf("%lld\n",dp[0]);
} I. Skr
回文自动机模板题，建一个回文自动机之后进行dfs即可。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5;
const int mod=1e9+7;
const int N = 10 ;
char str[MAXN];
struct Palindromic_Tree
{int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点int cnt[MAXN] ;int num[MAXN] ;int len[MAXN] ;//len[i]表示节点i表示的回文串的长度int S[MAXN] ;//存放添加的字符int last ;//指向上一个字符所在的节点，方便下一次addint n ;//字符数组指针int p ;//节点指针int newnode ( int l ) //新建节点{for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;cnt[p] = 0 ;num[p] = 0 ;len[p] = l ;return p ++ ;}void init () //初始化{p = 0 ;newnode ( 0 ) ;newnode ( -1 ) ;last = 0 ;n = 0 ;S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判fail[0] = 1 ;}int get_fail ( int x ) //和KMP一样，失配后找一个尽量最长的{while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;return x ;}void add ( int c ){c -= '0' ;S[++ n] = c ;int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置if ( !next[cur][c] ) //如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串{int now = newnode ( len[cur] + 2 ) ;//新建节点fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转next[cur][c] = now ;num[now] = num[fail[now]] + 1 ;}last = next[cur][c] ;cnt[last] ++ ;}void count (){for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！}
} A;
long long ten[MAXN];
void init2()
{ten[0]=1;for(int i=1; i<MAXN; i++)ten[i]=ten[i-1]*10%mod;
}
long long ans=0;void dfs(int d,int u,long long sum)
{for(int i=1; i<=9; i++)if(A.next[u][i]!=0){long long tmp=sum;int m=d+1;tmp=((sum*10%mod+i)%mod+i*ten[m]%mod)%mod;(ans+=tmp)%=mod;dfs(d+2,A.next[u][i],tmp);}
}void dfs1(int d,int u,long long sum)
{if(d==0){for(int i=1; i<=9; i++)if(A.next[u][i]!=0){ans+=i;ans%=mod;dfs1(1,A.next[u][i],i);}}elsefor(int i=1; i<=9; i++)if(A.next[u][i]!=0){long long tmp=sum;int m=d+1;tmp=((sum*10%mod+i)%mod+i*ten[m]%mod)%mod;(ans+=tmp)%=mod;dfs(d+2,A.next[u][i],tmp);}
}int main()
{init2();scanf("%s",str);int len=strlen(str);A.init();for(int i=0; i<len; i++)A.add(str[i]);A.count();dfs(0,0,0);dfs1(0,1,0);printf("%lld\n",ans);
} J. Sum
首先可以暴力筛掉不行的数，把可行的数放入数组里面，如果暴力枚举两个数判断是否大于n会T，那么这里可以用尺取法来减少一个枚举。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7+5;
bool vis[maxn];
vector<int>V;
void init()
{for(int i=2;i<maxn;i++){if(1LL*i*i>=maxn)break;int tmp=i*i;for(int k=1;1LL*tmp*k<maxn;k++)vis[tmp*k]=1;}for(int i=1;i<maxn;i++)if(vis[i]==0)V.push_back(i);//for(int i=0;i<10;i++)cout<<V[i]<<endl;
}int main()
{init();int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);long long ans=0;int now=V.size()-1;for(int i=0;i<V.size();i++){if(V[i]>n)break;int tmp=V[i];while(now>=0&&1LL*tmp*V[now]>n)now--;//cout<<now<<endl;ans+=now+1;}printf("%lld\n",ans);}return 0;}L. Magical Girl Haze
dijkstra的过程中再加一个状态表示当前已经免费了几条边即可。
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = (int)1e5 + 500, K = 11;
const ll INF = (ll)1e18;
typedef pair<int, int> Pii;
typedef pair<ll, Pii> P;struct edge{int to, cost;edge(int _to, int _cost){to = _to, cost = _cost;}
};int n, m, k, a, b, c;
ll dis[K][N];
vector<edge> G[N];void dijkstra(){for(int i = 0; i <= k; i++) fill(dis[i], dis[i]+N, INF);dis[0][0] = 0;priority_queue<P, vector<P>, greater<P> > pque;pque.push({
0, {
0, 0}});while(!pque.empty()){P p = pque.top(); pque.pop();int i = p.second.first, ki = p.second.second;ll dist = p.first;if(dist > dis[ki][i]) continue;for(edge e : G[i]){if(e.cost + dis[ki][i] < dis[ki][e.to]){dis[ki][e.to] = e.cost + dis[ki][i];pque.push({dis[ki][e.to], {e.to, ki}});}if(ki + 1 <= k && dis[ki][i] < dis[ki+1][e.to]){dis[ki+1][e.to] = dis[ki][i];pque.push({dis[ki+1][e.to], {e.to, ki+1}});}}}
}int main(){int T;scanf("%d", &T);while(T--){for(int i = 0; i < N; i++) G[i].clear();scanf("%d%d%d", &n, &m, &k);for(int i = 0; i < m; i++){scanf("%d%d%d", &a, &b, &c);a--, b--;G[a].push_back(edge(b, c));}dijkstra();ll res = INF;for(int i = 0; i <= k; i++) res = min(res, dis[k][n-1]);cout << res << endl;}
}