新年目标&&Noip2015题解
新的一年新气象，诸位好久不见？
自从去年NOI考砸了之后，我就正式退役了，连Noip都没有参加，期间，除了读书就是各种浪（当然是周末的时候啦），浪了大半年的，也有点疲倦了（实在是没有小说能看），于是打算开始做点正事（当然也是周末的时候啦），结果我悲剧地发现我竟然上不了自己的blog了（请容许我做一个悲伤的表情），好在后来发现是网络的缘故，所以这篇东西是我用流量发的TAT
先说点新年目标和新年愿望吧，去年元旦时候的目标还历历在目（虽然七八条中只有那么一两条达到了），今年就定下一些靠谱点的目标和愿望好了。
第一条是瘦下来，今年暑假我最重的时候达到了87.5kg，整个人就跟肉球一样，现在好不容易瘦到了80kg（请注意，这是一个月前的数据，因为很重要，所以要着重标明），但还是看上去很胖，所以新年的目标是瘦到70kg，以我的身高，这个体重刚好是标准体重的上界……
第二条当然是好好学习，高考考出个好成绩。
第三条、第三……咦，好像想不出第五条了，那就祝愿我和我的亲人还有所有我认识的以及认识我的人在新的一年里顺顺当当吧。
接下来是这篇文章的重点——2015年Noip题解（因为懒癌晚期的缘故，一直拖啊拖，我只能尽量保证这个学期内搞定……）。
估计有人会吐槽，都过去这么久了，发这种东西有意思么……主要是因为实在是找不到其他用来练手的东西了，像什么TopCoder div.2、Codeforces div.2真得是拿不出手（真实原因是我并不确定自己能够做出来），noip的难度正好（实际上是因为实在懒得想了可以轻易找到中文题解）。
Day 1
T1 无脑模拟，因为开始时没有看到第四条最后一句“否则”后面的话，结果出错了。
T2 一眼可以看出来就是求有向图上的最小圈，然后我觉得我不会做，去网上查无向图上最小圈的求法，查了一会儿突然想起来这是有向图关无向图毛事啊，于是我就会做了……而且，可以注意到，每个点有且只有一条出边，所以就直接无脑遍历用时间戳处理一下就行了。
import java.util.*;
public class P145 {
static final int N=51;
static int matrix[][]=new int[N][N];
public static void main(String args[]) {
Scanner cin=new Scanner(System.in);
int n=cin.nextInt();
int x=1,y=n/2+1;
matrix[x][y]=1;
for (int i=2;i<=n*n;i++) {
if ((x==1)&&(y!=n)) matrix[x=n][++y]=i;
else if ((y==n)&&(x!=1)) matrix[--x][y=1]=i;
else if ((x==1)&&(y==n)) matrix[++x][y]=i;
else if ((x!=1)&&(y!=n)&&(matrix[x-1][y+1]==0)) matrix[--x][++y]=i;
else matrix[++x][y]=i;
}
for (int i=1;i<=n;i++) {
for (int j=1;j<n;j++) System.out.print(matrix[i][j]+" ");
System.out.println(matrix[i][n]);
}
}
}
import java.io.*;
import java.util.*;
import java.lang.*;
public class P146 {
public static final int N=200010;
public static int n;
public static int ans=(int)1e9;
public static int p[]=new int[N];
public static int vis[]=new int[N];
public static int depth[]=new int[N];
public static int min(int x,int y) {return x<y?x:y;}
public static void dfs(int x,int tim) {
vis[x]=tim;
if (vis[p[x]]>0) {
if (vis[p[x]]!=tim) return;
ans=min(ans,depth[x]-depth[p[x]]+1);
return;
} else {
depth[p[x]]=depth[x]+1;
dfs(p[x],tim);
}
}
public static void main(String args[]) throws IOException {
StreamTokenizer cin=new StreamTokenizer(
new BufferedReader(new InputStreamReader(System.in)));
cin.nextToken();
n=(int)cin.nval;
for (int i=1;i<=n;i++) {
cin.nextToken();
p[i]=(int)cin.nval;
}
for (int i=1;i<=n;i++) if (vis[i]==0) dfs(i,i);
System.out.println(ans);
}
}
Day 2
T1 裸的二分答案，二分的过程中用贪心判断一下就行了，然而，刚开始时由于忘了考虑终点和最后一个石头之间的距离，只拿了97分（看到这个分数应该知道我是在哪里做的题了吧）。 PS：最近发现JAVA强行TLE，于是重新用C++写（抄）了一遍。
T2 本来说是期末考后就搞定的，然而寒假期间由于一直在刷作业和玩某卡牌游戏，极度颓废，然后直到今天……其实是简单的DP题，我的做法是f[i][j][k][0]表示从A串的前i个字母中选出k个字符串组成B串的前j个字符串的方案数，最后的0表示不选择A的第i个字符，1表示选择A串的第i个字符，那么如果A串的第i个字符和B串的第j个字符相同，那么就有f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k][1]，否则f[i][j][k][1]=0。不管怎样都有f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]。因为怕爆内存，所以第一维用了滚动数组。其他细节上的内容可以看我的程序。（PS：对于Java字符串处理的速度我已经绝望了，所以最后还是用了C++）
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N=50010;
int l,n,m,d[N];
bool check(int x) {
int last=0,cnt=m;
for (int i=1;i<=n;i++) {
if (p[i]-last<x) cnt--;
else last=p[i];
} return cnt>=0;
}
int check(int l,int r) {
int t=0;
while (l<=r) {
int mid=(l+r)>>1;
if (check(mid)) l=(t=mid)+1;
else r=mid-1;
} return t;
}
int main() {
scanf("%d%d%d",&l,&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&d[i]);
d[++n]=l;
cout<<check(0,l)<<endl;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int P=1000000007;
int n,m,t;
int f[2][205][205][2]; // A的前i个字符中选出k个字符串组成B的前j个字符
char a[1005],b[205];
int main() {
scanf("%d%d%d",&n,&m,&t);
scanf("%s%s",a+1,b+1);
f[0][0][0][0]=1;
for (int i=1;i<=n;i++) {
int id=i&1;
f[id][0][0][0]=1;
for (int j=1;j<=m;j++) {
for (int k=0;k<=t;k++) {
f[id][j][k][0]=f[id][j][k][1]=0;
if (a[i]==b[j]) {
if (k>0) f[id][j][k][1]=(f[id][j][k][1]+f[id^1][j-1][k-1][0])%P;
if (k>0) f[id][j][k][1]=(f[id][j][k][1]+f[id^1][j-1][k-1][1])%P;
f[id][j][k][1]=(f[id][j][k][1]+f[id^1][j-1][k][1])%P;
}
f[id][j][k][0]=(f[id][j][k][0]+f[id^1][j][k][0])%P;
f[id][j][k][0]=(f[id][j][k][0]+f[id^1][j][k][1])%P;
}
}
} printf("%d\n",(f[n&1][m][t][0]+f[n&1][m][t][1])%P);
return 0;
}
2022年8月20日 19:42
Secondary Education Core | Bellevue University 2021. Bellevue teachers vote to pause expansion of in-person learning 2021. bruin login Parents grow frustrated with Bellevue teachers meeting over. Parents grow frustrated with Bellevue teachers meeting over 2021
2022年9月09日 21:17
Formative Assessment means not only an examination, it includes various aspects such as Examination in completed lessons, Reflections, Project work done on the allotted topic and Self also Prepared notes etc. AP SSC fa 1 Question Paper Candidates of Telugu Medium, English Medium & Urdu Medium of the AP State can download the AP 10th Class FA 4 Model Paper 2023 Pdf with answers for the regular exams conducted by the Directorate of Government Examinations, Andhra Pradesh.